import java.util.Scanner;
 
 
class Solution {
    static int Answer;
 
    static int[][] map = new int[16][16]; // 행, 열
    static int[][] visited = new int[16][16]; // 행, 열
    static boolean findPath ;
     
    public static void main(String args[]) throws Exception {
         
         
        Scanner sc = new Scanner(System.in);
         
        for(int T=1; T <=10; T++) {
             
            // Test 번호
            sc.nextLine(); 
            int startX = -1, startY = -1;
             
            //map에 데이터 입력
            for(int i=0; i<16; i++) { // 행(y)
                String rowInput = sc.nextLine();
                for(int j=0; j<16; j++) { // 열(x)
                    // j => x , i => y
                    map[i][j] = rowInput.charAt(j) - '0';
                    visited[i][j] = 0;
                    if(map[i][j] == 2) {
                        startY = i;
                        startX = j;
                    }
                }
            }
             
            findPath = false;
            findView(startY, startX);
             
            System.out.println(String.format("#%d %d", T, findPath ? 1:0));
        }
         
    }
     
    public static void findView(int y, int x) {
        // 1, -1이 겹치지 않게 방향설정 (왼쪽, 아랫쪽, 오른쪽, 위쪽)
        int[] rotX = {-1,0,1,0};
        int[] rotY = {0,1,0,-1};
         
        // 도킹
        visited[y][x] = 1;
        int newX, newY;
        for(int i=0; i<4; i++) {
            // 왼쪽, 아랫쪽, 오른쪽, 위쪽을 우선순위로 탐색
            newX = x + rotX[i];
            newY = y + rotY[i];
            if(isWay(newY, newX)) { // 길이 있는 경우면 전진
                 
                // 도중에 출구를 발견한 경우
                if(map[newY][newX]==3) {
                    findPath = true;
                    break;
                }
                 
                findView(newY, newX); // 무한 재귀호출
            }
        }
        // 도킹 해제
        visited[y][x] = 0;
    }
     
    public static boolean isWay(int y, int x) {
        if(x<0 || x>15 || y<0 || y>15) { // 배열 범위를 넘어서는 경우
            return false;
        }else if(visited[y][x]==1){ // 지나온 곳은 통과할 수 없다.
            return false;
        }else if(map[y][x]==1) { // 벽은 통과할 수 없다.
            return false;
        }else if(findPath) {
            // 이미 길을 찾은 경우 break point 재귀함수를 모두 종류하기 위하여
            return false;
        }
        return true;
    }
     
}


+ Recent posts