这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1253
话说这题似乎是入门级的BFS。。。 只不过由一般的二维转变成了三维,所以搜索方向由上下左右变成了上下左右前后。 另外,这里要注意剪枝,虽然没剪枝也可以过,但是剪枝后可以减少近一半的时间。
// HDOJ 1253
// Author: Tanky Woo
// BFS
#include
#include
using namespace std;
int Castle[51][51][51]; // the castle
int vis[51][51][51]; // have visited
int dir[6][3]={ // direction
{0, 0, 1}, // up
{0, 0, -1}, // down
{1, 0, 0}, // left
{-1, 0, 0}, // right
{0, 1, 0}, // front
{0, -1, 0}, // after
};
int A, B, C, T, nCases;
typedef struct node
{
int x, y, z;
int step;
}Node;
void BFS()
{
memset(vis, 0, sizeof(vis));
vis[0][0][0] = 1;
queue Que;
Node pre, last;
pre.x = pre.y = pre.z = pre.step = 0;
Que.push(pre);
while(!Que.empty())
{
pre = Que.front();
Que.pop();
if(pre.step > T) // 剪枝一
break;
if(abs(A-1-pre.x) + abs(B-1-pre.y) + abs(C-1-pre.z) > T) //剪枝二,这个剪枝使时间减少了500ms。
break;
if(pre.x==A-1 && pre.y==B-1 && pre.z==C-1)
{
printf("%d\n", pre.step);
return;
}
for(int i=0; i<6; ++i)
{
last.x = pre.x+dir[i][0];
last.y = pre.y+dir[i][1];
last.z = pre.z+dir[i][2];
last.step = pre.step+1;
if(last.x>=0 && last.x=0 && last.y**=0 && last.z<C
&& !vis[last.x][last.y][last.z]
&& Castle[last.x][last.y][last.z]!=1)
{
vis[last.x][last.y][last.z] = 1;
Que.push(last);
}
}
}
printf("-1\n");
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &nCases);
while(nCases--)
{
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", &Castle;[i][j][k]);
BFS();
}
return 0;
}