Untitled
unknown
plain_text
a year ago
2.8 kB
5
Indexable
package phoneList; import java.io.FileInputStream; import java.util.Scanner; class Point{ int x, y, z; public Point() { // TODO Auto-generated constructor stub } public Point(int x, int y, int z){ this.x = x; this.y = y; this.z = z; } } class myQ{ int front, rear; Point[] a = new Point[10000000]; public myQ() { front = rear = -1;// TODO Auto-generated constructor stub } void init(){ front = rear = -1; } void enQueue(Point x){ a[++rear] = x; } Point deQueue(){ return a[++front]; } boolean isEmpty(){ return front == rear; } } public class Solution { public static int[] rs = {-1,0,1,0,0,0}; public static int[] cs = {0,-1,0,1,0,0}; public static int[] hs = {0,0,0,0,1,-1}; public static int N, T, ans, count; public static int[][][] a, visited; public static Point start, p; public static myQ queue = new myQ(); public static void main(String[] args) throws Exception { // TODO Auto-generated method stub System.setIn(new FileInputStream("src\\phoneList\\input.txt")); 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]; // visited = new int[N][N][N]; for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { a[i][j][k] = sc.nextInt(); if(a[i][j][k] == 2){ start = new Point(i,j,k); } } } } ans = 1000000; BFS(start); System.out.print("#" + tc + " "); System.out.println(ans); } } public static void BFS(Point start) { queue.init(); visited = new int[N][N][N]; queue.enQueue(start); visited[start.x][start.y][start.z] = 1; int cr, cc, ch; while(!queue.isEmpty()){ p = queue.deQueue(); if(p.x == 0 || p.y == 0 || p.y == N-1 || p.z == 0 || p.z == N-1){ if(ans > visited[p.x][p.y][p.z] - 1){ ans = visited[p.x][p.y][p.z] - 1; // System.out.println(ans + "*"); // for (int i = 0; i < N; i++) { // for (int j = 0; j < N; j++) { // for (int k = 0; k < N; k++) { // System.out.print(visited[i][j][k] + " "); // } // System.out.println(); // } // System.out.println(); // } } continue; } for (int i = 0; i < 6; i++) { cr = p.x + rs[i]; cc = p.y + cs[i]; ch = p.z + hs[i]; if(cr>=0&&cr<N&&cc>=0&&cc<N&&ch>=0&&ch<N && (visited[cr][cc][ch] == 0 || visited[p.x][p.y][p.z] + a[cr][cc][ch] < visited[cr][cc][ch])){ visited[cr][cc][ch] = visited[p.x][p.y][p.z] + a[cr][cc][ch]; queue.enQueue(new Point(cr,cc,ch)); } } } } }
Editor is loading...
Leave a Comment