</center>输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.(如果对输入描述不清楚,可以参考Sample Input中的迷宫描述,它表示的就是上图中的迷宫)
特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.
对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.
1 3 3 4 20 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0
11
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
#include <iostream> #include <vector> #include <string> #include <queue> #include <algorithm> #include <cmath> #include <ctime> #include <cstdio> #include <sstream> #include <deque> #include <functional> #include <iterator> #include <list> #include <map> #include <memory> #include <stack> #include <set> #include <numeric> #include <utility> #include <cstring> using namespace std; int A, B, C, T; struct point { int x, y, z; int t; point(int x=0, int y=0, int z=0, int t=0): x(x), y(y), z(z), t(t) {} }; int direct[][3] = {{1,0,0}, {-1,0,0}, {0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}}; int Map[55][55][55]; int BFS() { queue<point> que; que.push(point(0,0,0,0)); while(que.size()) { point p = que.front(); que.pop(); if(p.t > T) continue; if(p.x == A-1 && p.y == B-1 && p.z == C-1) return p.t; for(int k=0; k<6; ++k) { int nx = p.x + direct[k][0]; int ny = p.y + direct[k][1]; int nz = p.z + direct[k][2]; if(nx >=0 && nx<A && ny>=0 && ny<B && nz>=0 && nz<C && Map[nx][ny][nz] == 0) { que.push(point(nx, ny, nz, p.t+1)); Map[nx][ny][nz] = 1; } } } return - 1; } int main() { int K; scanf("%d", &K); while(K--) { scanf("%d%d%d%d", &A, &B, &C, &T); for(int a=0; a<A; ++a) for(int b=0; b<B; ++b) for(int c=0; c<C; ++c) scanf("%d", &Map[a][b][c]); printf("%d\n", BFS()); } return 0; }