[白俊/python]10026赤色薬

https://www.acmicpc.net/problem/10026

アルゴリズム分類

BFS

問題を解く

コードが少し乱れています.
基本的なbfsアルゴリズムで解く.
bfs関数でRグループの個数を計算します.全部加えました.
copylistはGをRに変換するリストです.

ソースコード

from collections import deque

dx=[1,-1,0,0]
dy=[0,0,1,-1]

def bfs(a,b,check):
  visited=[]
  visited.append((a,b))
  queue=deque()
  queue.append((a,b))

  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=n or ny<0 or ny>=n:
        continue
      elif graph[nx][ny] == check and (nx,ny) not in visited:
        graph[nx][ny]=0
        visited.append((nx,ny))
        queue.append((nx,ny))
  return 1

def bfs2(a,b,check):
  visited=[]
  visited.append((a,b))
  queue=deque()
  queue.append((a,b))

  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=n or ny<0 or ny>=n:
        continue
      elif copy[nx][ny] == check and (nx,ny) not in visited:
        copy[nx][ny]=0
        visited.append((nx,ny))
        queue.append((nx,ny))
  return 1

n=int(input())
graph=[]
for i in range(n):
  graph.append(list(input()))

copy=[[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if graph[i][j]=='G':
      copy[i].append('R')
    else:
      copy[i].append(graph[i][j])


result=[]
cnt=0
for i in range(n):
  for j in range(n):
    if graph[i][j]=='R':
      graph[i][j]=0
      bfs(i,j,'R')
      cnt+=1
    if graph[i][j]=='G':
      graph[i][j]=0
      bfs(i,j,'G')
      cnt+=1
    if graph[i][j]=='B':
      graph[i][j]=0
      bfs(i,j,'B')
      cnt+=1
result.append(cnt)

cnt=0
for i in range(n):
  for j in range(n):
    if copy[i][j]=='R':
      copy[i][j]=0
      bfs2(i,j,'R')
      cnt+=1
    if copy[i][j]=='B':
      copy[i][j]=0
      bfs2(i,j,'B')
      cnt+=1
result.append(cnt)

print(' '.join(map(str,result)))