[BFS|DFS]HDU 1253 胜利大逃亡


搜索题,三维BFS,设定前后上下左右6个方向搜索

1、要考虑当map[A-1][B-1][C-1]是1的情况, if(map[a-1][b-1][c-1]==1) {printf("-1n");continue;}

2、要认清剪枝的重要性,剪枝非常有利于提高代码的效率,就这题而言,若没有if(a+b+c-3>t) {printf("-1n");continue;}(起点与终点间最短路径大于时间限度),虽然没超时,但要937MS,加上这句后效率迅速提高到500MS,差不多提高了两倍

#include
#include
#include
int a,b,c,t,i,j,k,flag;
int q[130000],dis[13000];
int dir[6][3]={{0,0,1},{0,0,-1},{-1,0,0},{1,0,0},{0,1,0},{0,-1,0}};
int data[55][55][55],visit[55][55][55];
void bfs(int x,int y,int z)
{
    int front=0,rear=0;
    int C=z*b*c+y*c+x;
    visit[z][y][x]=1;
    q[rear++]=C;
    while(front=0 && nx=0 && ny=0 && nz
					

发表评论