首页 > 代码库 > HDU1253

HDU1253

一个简单的三维BFS:

刚开始说内存超出了,就把 标记走过的路语句 和 判断到达终点的语句 放在了push(next)之前

#include <cstdio>#include <cstring>#include <iostream>#include <queue>#define N 51using namespace std;struct node{    int x,y,z;    int t;};int dir[8][3]={{0,0,1},{0,1,0},{1,0,0},{0,0,-1},{0,-1,0},{-1,0,0}};int a,b,c;int T;int sa,sb,sc;int maze[N][N][N];bool judge(int x,int y,int z,int t){    if(x<0||x>=a||y<0||y>=b||z<0||z>=c) {            return 1;    }    if(t>T)               return 1;    if(maze[x][y][z]==1)  return 1;    return 0;}int bfs(){    queue<node> myque;    node now,next;    now.x=sa;    now.y=sb;    now.z=sc;    now.t=0;    myque.push(now);    while(!myque.empty())    {        now=myque.front();        myque.pop();        for(int i=0;i<8;i++)        {            next.x=now.x+dir[i][0];            next.y=now.y+dir[i][1];            next.z=now.z+dir[i][2];            next.t=now.t+1;            if(judge(next.x,next.y,next.z,next.t))            {                continue;            }            if(next.x==a-1&&next.y==b-1&&next.z==c-1) {                return next.t;            }            maze[next.x][next.y][next.z]=1;            myque.push(next);        }    }    return -1;}int main(){   int times;   scanf("%d",×);   while(times--){        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]);                }            }       }       sa=0;       sb=0;       sc=0;       int anw;       anw=bfs();       printf("%d\n",anw);   }}