Untitled

/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package OnAdvanced;

import java.util.Scanner;

/**
 *
 * @author HI
 */
public class DeMenPhieuLuuKy {
    static int t,n,r,c,s;
    static int[][][] a = new int[n][n][n];
    static int[][][] visit = new int[n][n][n];
    static int oo = 99999999;
    static int[][] step = {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};
    static class Queue {
        int front, rear;
        int[] data = new int[9000001];
        public Queue() {
            front = rear = 0;
        }
        public void enQ(int n) {
            data[rear++] = n;
        }
        public int deQ() {
            return data[front++];
        }
        public int qPeek() {
            return data[front];
        }
        public boolean isEmpty() {
            if (front == rear) {
                return true;
            }
            return false;
        }
    }
    public static void BFS(int r,int c, int s ){
        Queue qx = new Queue();
        Queue qy = new Queue();
        Queue qz = new Queue();
        qx.enQ(r);
        qy.enQ(c);
        qz.enQ(s);
        visit[r][c][s] = 0;
        while(!qx.isEmpty() && !qy.isEmpty() && !qz.isEmpty()){
            int nx = qx.deQ();
            int ny = qy.deQ();
            int nz = qz.deQ();
            for(int i = 0 ; i < 6 ; i++){
                int tmpx = nx+step[i][0];
                int tmpy = ny+step[i][1];
                int tmpz = nz+step[i][2];
                if(tmpx >=0 && tmpx < n 
                        && tmpy >=0 && tmpy < n
                        && tmpz >=0 && tmpz < n
                        && visit[tmpx][tmpy][tmpz] >= visit[nx][ny][nz] + 1){
                    if(a[tmpx][tmpy][tmpz] == 0){
                        visit[tmpx][tmpy][tmpz] = visit[nx][ny][nz];
                    }
                    else if(a[tmpx][tmpy][tmpz] == 1){
                        visit[tmpx][tmpy][tmpz] = visit[nx][ny][nz] + 1;
                    }
                    qx.enQ(tmpx);
                    qy.enQ(tmpy);
                    qz.enQ(tmpz);
                }
            }
        }
        
    }
    public static int solve(){
        int res = 99999999;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                for(int k = 0 ; k < n ; k++){
                    if(visit[i][j][k] < res
                            && i!= r 
                            && j !=c 
                            && k != s
                            && j!= n-1){
                        res = visit[i][j][k];
                    }
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        for(int tc = 1 ;tc <= t ; tc++){
            n = sc.nextInt();
            a = new int[n][n][n];
            visit = new int[n][n][n];
            for(int i = 0 ; i < n ; i++){
                for(int j = 0 ; j < n ; j++){
                    for(int k = 0 ; k < n ; k++){
                        visit[i][j][k] = oo;
                    }
                }
            }
            for(int i = 0 ; i < n ; i++){
                for(int j = 0 ; j < n ; j++){
                    for(int k = 0 ; k < n ; k++){
                        a[i][j][k] = sc.nextInt();
                        if(a[i][j][k] == 2){
                            r = i;
                            c = j;
                            s = k;
                        }
                    }
                }
            }
            BFS(r, c, s);
            System.out.println("#"+tc+" "+(solve()));
        }
    }
}