杭电 hdu 1253 胜利大逃亡

三维广搜，因为数据量很大，所以要用scanf 和 printf，否则注定要超时。但是也因为数据量很大的，所以数据并不刁钻，没有多少边界数据，所以很多剪枝用了都没有效果。直接用广搜的模板修改即可通过了。

/* THE ROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//

        URL   : http://poj.org/problem?id=2243
        Name  : Knight Moves

        Date  : Tuesday, April 20, 2010
        Time Stage : 0:14

        Result:
3846143 2011-04-20 22:12:10 Accepted 1253 952MS 1588K 4083 B C++ pyy

Test Data:

//----------------------------------------------------------------------------*/
#include <iostream>
#include <queue>
#include <string.h>
#include <stdio.h>
using namespace std;
struct node
{
        int x, y, z;
};
const int maxSize = 55,
          directions[][3] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1},
                              {-1, 0, 0}, {0, -1, 0}, {0, 0, -1} };
int blocks, rows, columns, backTime;
int map[maxSize][maxSize][maxSize],
    path[maxSize][maxSize][maxSize];

void out( node a )
{
        printf("%d, %d, %d/n", a.x, a.y, a.z );
}

void bfs()
{
        // the door is wall
        if( map[blocks-1][rows-1][columns-1] )
        {
                path[blocks-1][rows-1][columns-1] = -1;
                return ;
        }
        // start point is door
        if( blocks * rows * columns == 1 && !map[0][0][0] )
        {
                path[blocks-1][rows-1][columns-1] = 0;
                return ;
        }
        memset( path, 0, sizeof( path ) );
        // mark the start point
        path[0][0][0] = 1;

        int i, j, k, m;
        queue<node> q;
        node n;
        n.x = 0; n.y = 0; n.z = 0;
        q.push( n );

        while( !q.empty() )
        {
                n = q.front();
                q.pop();

                for( i = 0; i < 6; i++ )
                {
                        node tmp;
                        tmp.x = n.x + directions[i][0];
                        tmp.y = n.y + directions[i][1];
                        tmp.z = n.z + directions[i][2];
                        // border check
                        if( tmp.x < 0 || tmp.y < 0 || tmp.z < 0 || blocks <= tmp.x || rows <= tmp.y || columns <= tmp.z )
                                continue;
                        // already visited
                        if( map[tmp.x][tmp.y][tmp.z] || path[tmp.x][tmp.y][tmp.z] )
                                continue;
                        // visited it
                        path[tmp.x][tmp.y][tmp.z] = path[n.x][n.y][n.z] + 1;
                        if( path[tmp.x][tmp.y][tmp.z] > backTime )
                        {
                                path[blocks-1][rows-1][columns-1] = -1;
                                return ;
                        }
                        q.push( tmp );
                        // hit terminus
                        if( tmp.x == blocks - 1 && tmp.y == rows - 1 && tmp.z == columns - 1 )
                        {
                                --path[blocks-1][rows-1][columns-1];
                                return ;
                        }
                }
        }
        path[blocks-1][rows-1][columns-1] = -1;
}

int main()
{
        int i, j, k, tcase;
        while( cin >> tcase )
        {
                while( tcase-- )
                {
                        cin >> blocks >> rows >> columns >> backTime;
                        for( i = 0; i < blocks; i++ )
                                for( j = 0; j < rows; j++ )
                                        for( k = 0; k < columns; k++ )
                                                scanf("%d", &map[i][j][k]);

                        bfs();
                        printf("%d/n", path[blocks-1][rows-1][columns-1]);

                }
        }
        return 0;
}