HDu 1253勝利大逃亡(BFS)


    :      bfs          ,             ,                  ,      。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
#define inf 0x3f3f3f3f //         
int k,a,b,c,t;
int map[60][60][60];    //    
int time[60][60][60];	//    
struct point
{
    int x,y,z;
};
queue<point>P;

int dx[6] = {0,0,0,0,1,-1};	//      
int dy[6] = {0,0,1,-1,0,0};
int dz[6] = {1,-1,0,0,0,0};
int bfs( point s )
{
    memset(time,0x3f,sizeof(time));  //              
    time[0][0][0] = 0;
    int i;
    P.push( s );
    point hd;//     
    while( !P.empty())
    {
        hd = P.front();		//     
        P.pop();		//       
        if(hd.x==a-1 && hd.y==b-1 && hd.z == c-1) break;
        for(i=0;i<6;i++)
        {
            int x = hd.x + dx[i];
            int y = hd.y + dy[i];
            int z = hd.z + dz[i];
            if(x>=0 && x<=a-1 && y>=0 && y<=b-1 && z>=0 && z<=c-1 && map[x][y][z]==0 && time[x][y][z]==inf)  //            
            {
                point t;
                t.x = x; t.y=y; t.z=z;	//      ,         
                P.push(t);
                time[x][y][z] = time[hd.x][hd.y][hd.z] +1;

            }
        }
    }
    return time[a-1][b-1][c-1];
}
int main()
{
    //freopen("test.txt","r",stdin);
    int i,j,r;

    int min;
    point start;
    start.x = 0; start.y = 0; start.z = 0;//    
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d%d%d%d",&a,&b,&c,&t);
        for(i=0;i<a;i++)
        {
            for(j=0;j<b;j++)
            {
                for(r=0;r<c;r++)
                {
                    scanf("%d",&map[i][j][r]);
                }
            }
        }
        /*for(i=0;i<a;i++)
        {
            for(j=0;j<b;j++)
            {
                for(r=0;r<c;r++)
                {
                    printf("%d",map[i][j][r]);
                }
                printf("
"); } }*/ //printf("%d %d %d %d",a,b,c,t); if(map[a-1][b-1][c-1]==1) {printf("-1
");continue;} if(a+b+c-3>t) {printf("-1
");continue;} min = bfs(start); if(min<=t) printf("%d
",min); else printf("-1
"); } //cout << "Hello world!" << endl; return 0; }