Bai 2 giai
lalisadnn
plain_text
a year ago
2.6 kB
3
Indexable
#include <iostream> using namespace std; #define inf 1000000 #define Size 31 int N; int A[Size][Size][Size]; int D[Size][Size][Size]; int Q[inf], front, rear; int Ans; int sx,sy,sz; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int dz[] = {1,-1}; void BFS(int a, int b, int c) { front = rear = 0; Q[rear++] = a; Q[rear++] = b; Q[rear++] = c; D[a][b][c] = 0; while(front != rear) { int z = Q[front++]; int x = Q[front++]; int y = Q[front++]; for(int i = 0; i<4; i++) { int X = x + dx[i]; int Y = y + dy[i]; if(X<=0 || Y<=0 || X>N || Y>N || A[z][X][Y] == 2) continue; int temp = D[z][x][y] + A[z][X][Y]; if(temp < D[z][X][Y]) { D[z][X][Y] = temp; Q[rear++] = z; Q[rear++] = X; Q[rear++] = Y; } } for(int i = 0; i<2; i++) { int Z = z + dz[i]; if(Z<=0 || Z>N || A[Z][x][y] == 2) continue; int temp = D[z][x][y] + A[Z][x][y]; if(temp < D[Z][x][y]) { D[Z][x][y] = temp; Q[rear++] = Z; Q[rear++] = x; Q[rear++] = y; } } } } void Check() { for(int i = 1; i <= N; i ++) for(int j = 1; j <= N; j++) { if(D[1][i][j]!= inf && D[1][i][j] < Ans) Ans = D[1][i][j]; if(D[N][i][j]!= inf && D[N][i][j] < Ans) Ans = D[N][i][j]; if(D[i][1][j] != inf && D[i][1][j] < Ans) Ans = D[i][1][j]; if(D[i][j][1] != inf && D[i][j][1] < Ans) Ans = D[i][j][1]; if(D[i][j][N]!= inf && D[i][j][N] < Ans) Ans = D[i][j][N]; } } int main() { //freopen("Demen.txt", "r", stdin); int T; cin >> T; int tc; for (tc = 1; tc <= T; tc ++) { cin >> N; for(int i = 1; i <= N; i++) { for (int j = 1; j<= N; j++) { for(int k = 1; k <=N; k ++) { cin >> A[i][j][k]; D[i][j][k] = inf; if(A[i][j][k] == 2) { sz = i; sx = j; sy = k; } } } } Ans = inf; BFS(sz,sx,sy); Check(); cout << "#" << tc << " " << Ans << endl; } return 0; }
Editor is loading...
Leave a Comment