Bai 2 giai

 avatar
lalisadnn
plain_text
2 months ago
2.6 kB
1
Indexable
Never
#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;
}
Leave a Comment