白駿-赤色薬水(10026)



Graph + DFS


質問する


赤緑の薬水はほとんど赤緑の違いを感じない.そのため、赤緑色の弱い人が見る絵とは違います.
サイズN×Nインチメッシュの各格子には、R(赤)、G(緑)、B(青)を塗った図があります.図はいくつかの領域に分けられ、領域は同じ色で構成されています.また、同じ色が上下左右に隣接している場合、2文字は同じ領域に属する.(色の違いがほとんど感じられない場合は同じ色とも呼ばれます)
たとえば、図が次のように表示されている場合.
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
赤い薬ではない人から見れば、エリアの総数は4つです.(赤2、青1、緑1)しかし赤の人は3つのエリアを見ることができます.(赤-緑2、青1)
画像が入力されると、赤と非赤の人が見る領域数を求めるプログラムを作成します.

入力


1行目はNです.(1 ≤ N ≤ 100)
2行目からN行目に1枚の図が与えられます.

しゅつりょく


赤緑色薬ではない人が見た領域数と赤緑色薬の人が見た領域数を空白に分けて出力します.

正解のないコード
from collections import deque
def solution(relation):
    
    RGB = [['R', 'R', 'R', 'B', 'B'], ['G', 'G', 'B', 'B', 'B'], ['B', 'B', 'B', 'R', 'R'], ['B', 'B', 'R', 'R', 'R'], ['R', 'R', 'R', 'R', 'R']]
    n = 5
    result = [[], []]

    def BFS(x, y):
        counting = 1
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        color = RGB[x][y]

        queue = deque([])
        queue.append((x, y))

        while queue:
            x, y = queue.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if (0 <= nx < n) and (0 <= ny <n):
                    if RGB[nx][ny] == color:
                        RGB[nx][ny] = 1
                        queue.append((nx, ny))

        return counting

    for i in range(n):
        for j in range(n):
            if RGB[i][j] != 1:
                result[0].append(BFS(i, j))

    for i in range(n):
        for j in range(n):
            if RGB[i][j] == 'G':
                RGB[i][j] == 'R'

    for i in range(n):
        for j in range(n):
            if RGB[i][j] != 1:
                result[1].append(BFS(i, j))
            
    print(result)
    
    
    return True
通常、色盲配列が分かれた後
import sys
from collections import deque

n = int(sys.stdin.readline())
original = []
copy = [[0] * n for i in range(n)]
countA = 0
countB = 0

def BFS(x, y, List):
  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  color = List[x][y] # color => 상하좌우 비교할 때 동일여부 체크하기위한 장치
  List[x][y] = 0

  queue = deque([])
  queue.append((x, y))

  while queue:
    x, y = queue.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if (0 <= nx < n) and (0 <= ny < n):
        if List[nx]n[y] == color:
          List[nx][ny] = 0
          queue.append((nx, ny))

for i in range(n): # 정상인용
  original.append(list(map(str, input())))

for i in range(n): # copy 배열을 색맹용으로 설정
  for j in range(n):
    if original[i][j] == "R" or original[i][j] == 'G':
      copy[i][j] = 1 # R, G 같은 종류로 묶기
    else: # B는 다른 종류로 할당
      copy[i][j] = 2

for i in range(n): # 정상인용, 색맹용을 한꺼번에 BFS 돌린다.
  for j in range(n):
    if original[i][j] != 0:
      BFS(i, j, original)
      countA += 1 # 정상인용 영역의 R, G, B 종류 number
    if copy[i][j] != 0:
      BFS(i, j, copy)
      countB += 1 # 색맹용 영역의 (R, G), B 종류 number

print(countA, countB)
countA:通常の参照領域の数
県B:色盲用区域の数