https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYEXgKnKKg0DFARx

풀이

1. 색이 칠해져 있는 좌표를 큐에 넣는다. (bfs)
2. 큐에서 꺼낸 하나의 좌표에 대해서 다음과 같은 작업을 수행한다. 이 작업을 모든 칸이 칠해질 때 까지 반복한다.
   1. 좌표의 인접한 각 칸에 대해서
      1. 인접한 칸이 빈 칸일 경우 인접한 칸을 좌표의 색과 반대되는 색으로 칠한다.
      2. 인접한 칸이 색이 칠해져 있을 경우, 좌표의 색과 인접한 칸의 색이 같다면 안되는 경우이므로 impossible을 출력한다.
3. 작업을 마친 경우 ⇒ 색이 다 칠해졌을 경우, possible을 출력한다.

from collections import deque

T = int(input())

dRow = [-1,1,0,0]
dCol = [0,0,-1,1]
# 상 하 좌 우

def sol(T,board):
  visited = [[False] * len(board[0]) for _ in range(len(board))]
  queue = deque()
  for i in range(len(board)):
    for j in range(len(board[i])):
      if(board[i][j]!='?'):
        queue.append([i,j,board[i][j]]) 
        #  board 에서 이미 칠해진 칸을 큐에 넣는다. 
        visited[i][j] = True
  if(len(queue)==0):
    print('#{0} {1}'.format(T,"possible"))
    return

  while(len(queue)>0): #bfs실행
    [r,c,v] = queue.popleft()
    for i in range(4):
      nr = r+dRow[i]
      nc = c+dCol[i]
      if nr>=0 and nc>=0 and nr<len(board) and nc<len(board[0]): #유효성검사
        if board[nr][nc] == '?': #인접한 칸이 빈 칸일 경우 board[r][c]의 색과 반대색으로 칠한다. 
          board[nr][nc] = "#" if board[r][c]=="." else "."
          visited[nr][nc] = True
          queue.append([nr,nc,board[nr][nc]])
        else:
          if board[nr][nc] == board[r][c]: #인접한 칸의 색이 이미 칠해져 있을 경우, board[r][c]의 색과 반대 색이면 ok, 같은 색이면 impossible
            print('#{0} {1}'.format(T,"impossible"))
            return
  print('#{0} {1}'.format(T,"possible"))
  return
  
for i in range(1,T+1):
  [N,M] = list(map(int, input().split()))
  board = []
  for j in range(N):
    line = list(input())
    board.append(line)
  sol(i,board)