1227. 미로2

import sys
sys.stdin = open("미로2_input.txt")
 
def find_start(maze): # 시작점을 찾아주는 함수
    for i in range(N):
        for j in range(N):
            if maze[i][j] == 2:# 완전탐색을 이용하여 출발지부터 먼저 찾아준다.
                return i, j # 찾은 출발지 i, j 를 리턴 시켜준다.
 
def bfs(x, y):
    Q = []
    Q.append((x, y))    # enQ
    visited[x][y] = 1   # 방문체크
 
    while Q:
        x, y = Q.pop(0)   # deQ
        # 3인지 체크  return 1
        if maze[x][y] == 3:  # 출구이면 1 반환
            return 1
 
        for i in range(4): # 인접할 수 있는 정점은 4개
            nx, ny = x + dx[i], y + dy[i] # 방향설정
            if nx < 0 or nx == N: continue # 인덱스 체크
            if ny < 0 or ny == N: continue
            if visited[nx][ny] == 1 : continue # 방문체크
            if maze[nx][ny] == 1: continue # 벽체크
 
            Q.append((nx, ny))
            visited[nx][ny] = 1
 
    return 0 # 출구에 가지 못하고 모든 칸 방문
 
T = 10  # 테스트케이스
N = 100 # 미로판
dx = [-1, 1, 0, 0] # 가로 방향
dy = [0, 0, -1, 1] # 세로 방향
for tc in range(1, T+1): #테스트 케이스
    no = int(input()) # 테스트케이스 번호
    maze = [list(map(int, input())) for _ in range(N)]  # 미로의 데이터 값
    visited = [[0]*(N) for _ in range(N)]  # 방문체크
    sx, sy = find_start(maze) #시작점을 찾고 리턴 받은 i, j 값을 넣어준다.
    print("#{} {}".format(tc, bfs(sx, sy)))