奇葩！这么简单的广搜居然爆内存了，而且一直爆，一直爆，Orz
而且我也优化过了的啊，尼玛还是一直爆！
先把代码贴上睡觉去了，明天再来弄
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std; struct Point
{
int x, y, z;
int steps;
}start; int a, b, c, m;
int map[][][];
int dir[][] = {{,,}, {-,,}, {,,}, {,-,}, {,,}, {,,-}}; bool islegal(int x, int y, int z)
{
return (x>= && x<a && y>= && y<b && z>= && z<c && (map[x][y][z] == ));
} void BFS(void)
{
queue<Point> qu;
start.x = start.y = start.z = start.steps = ;
map[][][] = ;
qu.push(start);
while(!qu.empty())
{
Point fir = qu.front();
qu.pop();
if(fir.x==a- && fir.y==b- && fir.z==c-)
{printf("%d\n", fir.steps); return;}
if(fir.steps > m)
{printf("-1\n"); return;}
for(int i = ; i < ; ++i)
{
int xx = fir.x + dir[i][];
int yy = fir.y + dir[i][];
int zz = fir.z + dir[i][];
if(islegal(xx, yy, zz))
{
Point next;
next.x = xx, next.y = yy, next.z = zz;
next.steps = fir.steps + ;
map[zz][xx][yy] = ;
if(abs(xx-a+)+abs(yy-b+)+abs(zz-c+)+next.steps > m)
continue;
qu.push(next);
}
}
}
printf("-1\n");
} int main(void)
{
#ifdef LOCAL
freopen("1253in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d%d", &a, &b, &c, &m);
for(int i = ; i < a; ++i)
for(int j = ; j < b; ++j)
for(int k = ; k < c; ++k)
scanf("%d", &map[i][j][k]); BFS();
}
return ;
}
代码君
最终还是自己用数组模拟队列A过去了
一个优化：
因为题目要求在规定时间内走出迷宫，如果出口距离当前位置太远(即使在没有墙壁阻挡的情况下也走不到)，那么就可以直接输出-1了
这个优化让900+MS的运行时间减少到了500+MS，还是比较给力的
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = **+;
int head, tail;
struct Point
{
int x, y, z;
int steps;
}qu[maxn]; int a, b, c, m;
int map[][][];
int dir[][] = {{,,}, {-,,}, {,,}, {,-,}, {,,}, {,,-}}; bool islegal(int x, int y, int z)
{
return (x>= && x<a && y>= && y<b && z>= && z<c && (map[x][y][z] == ));
} void BFS(void)
{
qu[].x = qu[].y = qu[].z = qu[].steps = ;
head = , tail = ;
while(head < tail)
{
if(qu[head].steps > m)
{printf("-1\n"); return;}
if(qu[head].x==a- && qu[head].y==b- && qu[head].z==c-)
{printf("%d\n", qu[head].steps); return;}
for(int i = ; i < ; ++i)
{
int xx = qu[head].x + dir[i][];
int yy = qu[head].y + dir[i][];
int zz = qu[head].z + dir[i][];
if(islegal(xx, yy, zz))
{
map[xx][yy][zz] = ;
if(a+b+c--xx-yy-zz > m-qu[head].steps-) //优化
continue;
qu[tail].x = xx;
qu[tail].y = yy;
qu[tail].z = zz;
qu[tail++].steps = qu[head].steps + ;
}
}
++head;
}
printf("-1\n");
} int main(void)
{
#ifdef LOCAL
freopen("1253in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d%d", &a, &b, &c, &m);
for(int i = ; i < a; ++i)
for(int j = ; j < b; ++j)
for(int k = ; k < c; ++k)
scanf("%d", &map[i][j][k]); //map[0][0][0] = 1;
BFS();
}
return ;
}
代码君