hdu 1253 胜利大逃亡（BFS）

三维的BFS，刚开始一直超内存，超无语...... 改了n多次终于AC了

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <queue>

using namespace std;

int map[50][50][50];

int d[6][3] = { {1,0,0},{-1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1} };

int flag,x,y,z,num;

struct node

{

    int x,y,z;

    int time;

};

void bfs()

{

    queue <node> q;

    node s,temp;

    s.x = 0;

    s.y = 0;

    s.z = 0;

    s.time = 0;

    q.push(s);

    while(!q.empty())

    {

        temp = q.front();

        q.pop();

        if(temp.x == x - 1 && temp.y == y - 1 && temp.z == z - 1 && temp.time <= num)

        {

            printf("%d\n",temp.time);

            flag = 1;

            return ;

        }

        for(int i = 0 ; i < 6 ; i ++)

        {

            s = temp;

            s.x += d[i][0];

            s.y += d[i][1];

            s.z += d[i][2];

            if(s.x < 0 || s.x >= x || s.y < 0 || s.y >= y || s.z < 0 || s.z >= z || map[s.x][s.y][s.z] == 1)

             continue;

            s.time ++;

            if(s.time >= num && temp.x != x - 1 && temp.y != y - 1 && temp.z != z - 1 ) continue;

            map[s.x][s.y][s.z] = 1;

            q.push(s);

        }

    }

}

int main()

{

    int T,i,j,k;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d%d",&x,&y,&z,&num);

        for(i = 0 ; i < x ; i ++)

         for(j = 0 ; j < y ; j ++)

          for(k = 0 ; k < z ; k ++)

           scanf("%d",&map[i][j][k]);

        flag = 0;

        bfs();

        if(!flag) printf("-1\n");

    }

    return 0;

}

巴特西

hdu 1253 胜利大逃亡（BFS）

最新文章

热门文章