</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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int K,A,B,C,T;
int G[51][51][51];
int d[6][3] = {{1,0,0}, {0,1,0}, {0,0,1}, {-1,0,0}, {0,-1,0}, {0,0,-1}};
struct P{ int a,b,c; int t; P(int aa,int bb,int cc,int tt):a(aa),b(bb),c(cc),t(tt){}
};
int BFS()
{ queue<P> q; P s(0,0,0,0); q.push(s); while(!q.empty()) { P x = q.front(); q.pop(); for(int i=0;i<6;i++) { int aa = x.a + d[i][0]; int bb = x.b + d[i][1]; int cc = x.c + d[i][2]; int tt = x.t + 1; if(aa>=0 && aa<A && bb>=0 && bb<B && cc>=0 && cc<C && G[aa][bb][cc]!=1 && tt<=T) { if(aa==A-1 && bb==B-1 && cc==C-1) return tt; P y(aa,bb,cc,tt); q.push(y); G[aa][bb][cc] = 1; } } } return -1;
}
int main()
{ scanf("%d", &K); while(K--) { scanf("%d%d%d%d", &A,&B,&C,&T); for(int i=0;i<A;i++) for(int j=0;j<B;j++) for(int k=0;k<C;k++) scanf("%d", &G[i][j][k]); int t = BFS(); printf("%d\n", t); }
}
#include<bits/stdc++.h>
using namespace std;
int maze[50][50][50];
bool mark[50][50][50];
struct N{
int x,y,z;//坐标
int t;
};
queue<N>Q;
int go[][3]={
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1
};
int BFS(int a,int b,int c)//返回到达出口所需时间
{
while(!Q.empty())
{
N now=Q.front();
Q.pop();
for(int i=0;i<6;i++)//依次扩展其6个相邻节点
{
int x=now.x+go[i][0];
int y=now.y+go[i][1];
int z=now.z+go[i][2];
if(x<0||x>=a||y<0||y>=b||z<0||z>=c) continue;
if(mark[x][y][z]==true) continue;//包含该状态的点已经被访问过，丢弃
if(maze[x][y][z]==1) continue;//墙
N next;
next.x=x;
next.y=y;
next.z=z;
next.t=now.t+1;
Q.push(next);//新状态压入队列
mark[next.x][next.y][next.z]=true;//标记该点为访问过的
if(x==a-1&&y==b-1&&z==c-1) return next.t;
}
}
return -1;
}
int main(){
int K,A,B,C,T;
scanf("%d",K);
while(K--)
{
scanf("%d%d%d%d",&A,&B,&C,&T);
for(int i=0;i<A;i++)
for(int j=0;j<B;j++)
for(int z=0;z<C;z++)
{
scanf("%d",&maze[i][j][z])
mark[i][j][z]=false;
}
while(!Q.empty()) Q.pop();//清空队列
mark[0][0][0]=true;//标记起点
N tmp;
tmp.x=0;
tmp.y=0;
tmp.z=0;
Q.push(tmp);
int ret=BFS(A,B,C);
if(ret<=T&&ret!=-1) cout<<ret<<endl;
else cout<<"-1"<<endl;
}
return 0;
} 
#include<stdio.h>
#include<queue>
using namespace std;
bool mark[50][50][50]; //Tag array
int maze[50][50][50]; // Storage maze information
struct N
{
int x, y, z; // location
int t; // time
};
queue<N> Q;
int go[][3] = {
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1
};
int BFS(int a, int b, int c)
{
while (Q.empty() == false)
{
N now = Q.front();
Q.pop();
for (int i = 0; i < 6; i++)
{
int nx = now.x + go[i][0];
int ny = now.y + go[i][1];
int nz = now.z + go[i][2];
if (nx < 0 || nx >= a || ny < 0 || ny >= b || nz < 0 || nz >= c)
{
continue;
}
if (maze[nx][ny][nz] == 1)
{
continue;
}
if (mark[nx][ny][nz] == true)
{
continue;
}
N tmp;
tmp.x = nx;
tmp.y = ny;
tmp.z = nz;
tmp.t = now.t + 1;
Q.push(tmp);
mark[nx][ny][nz] = true;
if (nx == a - 1 && ny == b - 1 && nz == c - 1)
{
return tmp.t;
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int a, b, c, t;
scanf("%d%d%d%d", &a, &b, &c, &t);
for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
for (int k = 0; k < c; k++)
{
scanf("%d", &maze[i][j][k]);
mark[i][j][k] = false;
}
}
}
while (Q.empty() == false)
{
Q.pop();
}
mark[0][0][0] = true;
N tmp;
tmp.t = tmp.x = tmp.y = tmp.z = 0;
Q.push(tmp);
int res = BFS(a, b, c);
if (res <= t)
{
printf("%d\n", res);
}
else
{
printf("-1\n");
}
}
getchar();
return 0;
}
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
struct N {
int x, y, z;
int t;
};
int mark[50][50][50];//判断是否已经遍历过
int maze[50][50][50];//保存立方体信息
queue<N> Q;//广度优先搜索的队列
int mynext[6][3] = {
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1
};
int BFS(int a, int b, int c, int t) {//位置信息
while (Q.empty() == false) {
//队列非空，继续扩展
N now = Q.front();
Q.pop();//弹出队头
if (now.t > t) { break; }//超出时间则直接退出
for (int i = 0; i < 6; i++) {
int nx = now.x + mynext[i][0];
int ny = now.y + mynext[i][1];
int nz = now.z + mynext[i][2];
if (nx < 0 || nx >= a || ny < 0 || ny >= b || nz < 0 || nz >= c) continue;
if (maze[nx][ny][nz] == 1) continue;//若该位置为墙，则丢弃
if (mark[nx][ny][nz] == 1) continue;//若已经搜索到过，则丢弃
N tmp;
tmp.x = nx;
tmp.y = ny;
tmp.z = nz;
tmp.t = now.t + 1;
Q.push(tmp);
mark[nx][ny][nz] = 1;
if (nx == a - 1 && ny == b - 1 && nz == c - 1) return tmp.t;
}
}
return 2000;//若无法到达终点或者超越了时间限制，则返回一个比题目T的最大值还要大的时间，用于判断输出
}
int main() {
int m;
scanf("%d",&m);
while (m--) {
int a, b, c, t;
//cin >> a >> b >> c >> t;
scanf("%d%d%d%d", &a,&b,&c,&t);
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
for (int q = 0; q < c; q++) {
//cin >> maze[i][j][q];
scanf("%d", &maze[i][j][q]);
mark[i][j][q] = 0;
}
}
}
while (Q.empty() == false) Q.pop();
N first;
first.x = first.y = first.z = 0;
first.t = 0;
Q.push(first);
int ans = BFS(a, b, c, t);
/*if (ans < t) cout << ans << endl;
else cout << -1 << endl;*/
if (ans>t)printf("-1\n"); else printf("%d\n", ans);
}
system("pause");
}
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 50+5;
int cube[maxn][maxn][maxn];
bool mark[maxn][maxn][maxn];
int direct[6][3] = {
{-1, 0, 0},
{1, 0, 0},
{0, -1, 0},
{0, 1, 0},
{0, 0, -1},
{0, 0, 1}
};
struct State {
int x, y, z;
int t;
// State(int x, int y, int z, int t)
};
queue<State> q;
int BFS(int a, int b, int c) {
while (!q.empty()) {
State now = q.front();
q.pop();
for (int i = 0; i < 6; i++) {
int next_x = now.x + direct[i][0];
int next_y = now.y + direct[i][1];
int next_z = now.z + direct[i][2];
if (next_x < 0 || next_x >= a || next_y < 0 || next_y >= b || next_z < 0 || next_z >= c) {
continue;
}
if (cube[next_x][next_y][next_z] == 1) continue;
if (mark[next_x][next_y][next_z]) continue;
State next;
next.x = next_x;
next.y = next_y;
next.z = next_z;
next.t = now.t + 1; //路径长度+1
q.push(next);
mark[next.x][next.y][next.z] = true;
if (next.x == (a-1) && next.y == (b-1) && next.z == (c-1)) {
return next.t;
}
}
}
return -1;
}
int main() {
int k;
scanf("%d", &k);
while (k--) {
int a, b, c, t;
scanf("%d%d%d%d", &a, &b, &c, &t);
//获取输入
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
for (int k = 0; k < c; k++) {
scanf("%d", &cube[i][j][k]);
mark[i][j][k] = false;
}
}
}
while (!q.empty()) q.pop();
State start;
start.x = start.y = start.z = start.t = 0;
mark[start.x][start.y][start.z] = true;
q.push(start);
int rtn = BFS(a, b, c);
if (rtn <= t) {
printf("%d\n", rtn);
}
else {
printf("-1\n");
}
}
return 0;
}
#include <stdio.h>
#include <queue>
using namespace std;
struct E{
int x,y,z;
int t;
};
queue<E> Q;
bool mark[50][50][50];
int maze[50][50][50];
int go[6][3]={
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1,
};
int BFS(int a, int b, int c){ //类似用队列进行层次遍历 不同之处在于 剪枝（对某些不满足条件的元素舍弃）
E newP;
while(!Q.empty()){
newP = Q.front();
Q.pop(); //拿出队头元素
for(int i=0; i<6; i++){
int nx = newP.x + go[i][0];
int ny = newP.y + go[i][1]; //某坐标的六个方向 相当于当前节点的下一层子树
int nz = newP.z + go[i][2];
if(mark[nx][ny][nz]) continue;
if(maze[nx][ny][nz]) continue;
if(nx<0 || ny<0 || nz<0 || nx>=a || ny>=b || nz>=c) continue;
newP.x = nx;
newP.y = ny;
newP.z = nz;
newP.t++;
mark[nx][ny][nz] = true;
Q.push(newP);
if(nx==a-1 && ny==b-1 && nz==c-1)
return newP.t;
}
}
return -1;
}
int main(){
int K;
while(scanf("%d", &K) != EOF){
while(K--){
int a, b, c, T;
scanf("%d %d %d %d", &a, &b, &c, &T);
for(int i=0; i<a; i++)
for(int j=0; j<b; j++)
for(int k=0; k<c; k++){
scanf("%d", &maze[i][j][k]); //迷宫初始化
mark[i][j][k] = false;
}
while(!Q.empty()) Q.pop(); //用于进行层次遍历的队列清空
E tmp;
tmp.x = tmp.y = tmp.z = tmp.t = 0;
Q.push(tmp); //从（0，0,0）出发
int ans = BFS(a,b,c);
if(ans < T) printf("%d", ans);
else printf("-1");
}
}
return 0;
}
using namespace std;
struct sta{
int x,y,z;
int t;
};
queue q;
int maze[51][51][51];
bool marked[51][51][51];
int go[][3]={
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1,
};
int bfs(int a,int b,int c){
sta cur;
while(q.empty()==false){
cur=q.front();
q.pop();
for(int i=0;i=0&&cur_y=0&&cur_z=0)
if(maze[cur_x][cur_y][cur_z]==0)
if(marked[cur_x][cur_y][cur_z]==false){
marked[cur_x][cur_y][cur_z]=true;
sta next;
next.x=cur_x;
next.y=cur_y;
next.z=cur_z;
next.t=cur.t+1;
q.push(next);
if(next.x==a-1&&next.y==b-1&&next.z==c-1)
return next.t;
}
}
}
return -1;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int a,b,c,t,ret;
while(n--){
scanf("%d%d%d%d",&a,&b,&c,&t);
for(int x=0;x<a;x++)
for(int y=0;y<b;y++)
for(int z=0;z<c;z++){
scanf("%d",&maze[x][y][z]);
marked[x][y][z]=false;
}
while(q.empty()==false) q.pop();
sta begin;
begin.x=begin.y=begin.z=begin.t=0;
q.push(begin);
marked[begin.x][begin.y][begin.z]=true;
ret=bfs(a,b,c);
printf("%d\n",ret<=t?ret:-1);
}
}
}
#include<stdio.h>
#include<queue>
#define MAX 50
using namespace std;
int space[MAX][MAX][MAX];
bool mark[MAX][MAX][MAX];
struct N{
int x,y,z;
int time;
};
queue<N> Q;
int go[][3]={
1,0,0,
-1,0,0,
0,1,0,
0,-1,0,
0,0,1,
0,0,-1,
};
int BFS(int a,int b,int c){
int i;
while(!Q.empty()){
N now;
int x,y,z;
now=Q.front();
Q.pop();
for(i=0;i<6;i++){
x=now.x+go[i][0];
y=now.y+go[i][1];
z=now.z+go[i][2];
if(x<0||x>=a||y<0||y>=b||z<0||z>=c) continue;
if(mark[x][y][z]==true) continue;
if(space[x][y][z]==1) continue;
N tmp;
tmp.x=x;
tmp.y=y;
tmp.z=z;
tmp.time=now.time+1;
Q.push(tmp);
mark[x][y][z]=true;
if(x==a-1&&y==b-1&&z==c-1) return tmp.time;
}
}
return -1;
}
int main(){
int n,a,b,c,t,i,j,k;
scanf("%d",&n);
while(n--){
scanf("%d%d%d%d",&a,&b,&c,&t);
for(i=0;i<a;i++)
for(j=0;j<b;j++)
for(k=0;k<c;k++){
scanf("%d",&space[i][j][k]);
mark[i][j][k]=false;
}
mark[0][0][0]=true;
while(!Q.empty())
Q.pop();
N tmp;
tmp.x=tmp.y=tmp.z=tmp.time=0;
Q.push(tmp);
int ans=BFS(a,b,c);
if(ans<=t)
printf("%d\n",ans);
else
printf("%d\n",-1);
}
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <iostream>
#include <ctype.h>
#include <string.h>
#include <set>
#include <stack>
#include<functional>
using namespace std;
#define Size 55
int ma[Size][Size][Size];
bool mark[Size][Size][Size];
struct N{
int x, y, z;
int t;
};
int a, b, c;
queue<N> q;
int go[][3] = { { 0, 0, 1 }, { 0, 0, -1 }, { 0, 1, 0 }, { 0, -1, 0 }, { 1, 0, 0 }, { -1, 0, 0 } };
int bfs(){
while (q.size()){
N tmp = q.front();
q.pop();
int x = tmp.x, y = tmp.y, z = tmp.z, t = tmp.t;
for (int i = 0; i < 6; i++){
N to;
to.x = x + go[i][0];
to.y = y + go[i][1];
to.z = z + go[i][2];
to.t = t + 1;
if (to.x < 0 || to.x >= a || to.y < 0 || to.y >= b || to.z < 0 || to.z >= c) continue;
if (mark[to.x][to.y][to.z]) continue;
if (ma[to.x][to.y][to.z]) continue;
if (to.x == a - 1 && to.y == b - 1 && to.z == c - 1) return to.t;
q.push(to);
mark[to.x][to.y][to.z] = 1;
}
}
return 0x3f3f3f;
}
int main(){
int n;
cin >> n;
while (n--){
while (q.size()) q.pop();
int t;
cin >> a >> b >> c >> t;
for (int i = 0; i < a; i++){
for (int j = 0; j < b; j++){
for (int k = 0; k < c; k++){
scanf("%d", &ma[i][j][k]);
mark[i][j][k] = 0;
}
}
}
N s;
s.x = s.y = s.z = 0;
s.t = 0;
q.push(s);
int ans = bfs();
if (ans < t) cout << ans << endl;
else cout << -1 << endl;
}
}
扫描二维码，关注牛客网
下载牛客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; }