hdu-1240

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/41485583

三维的BFS

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

using namespace std;

char str[10];
int n;
int sx,sy,sz;
int ex,ey,ez;
int ans ;

int vis[33][33][33];
char p[33][33][33];

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

struct node 
{
    int x,y,z;
    int step;
};

int bfs ()
{
    memset(vis,0,sizeof(vis));

    node qq,qqq;

    qq.x = sx;
    qq.y = sy;
    qq.z = sz;
    qq.step = 0;

    vis[qq.x][qq.y][qq.z] = 1;

    queue<node> q;
    q.push(qq);

    while (!q.empty())
    {
        qqq = q.front();
        q.pop();
        if (qqq.x == ex && qqq.y == ey && qqq.z == ez)
        {
            ans = qqq.step;
            return 1;
        }
        for(int i=0;i<6;i++)
        {
            qq.x = qqq.x + dir[i][0];
            qq.y = qqq.y + dir[i][1];
            qq.z = qqq.z + dir[i][2];
            qq.step = qqq.step;
            if (qq.x < 0 || qq.x >=n || qq.y < 0 || qq.y >=n || qq.z < 0 || qq.z >=n )
                continue;
            if(vis[qq.x][qq.y][qq.z] || p[qq.x][qq.y][qq.z]=='X')
                continue;

            vis[qq.x][qq.y][qq.z] = 1;
            qq.step = qqq.step + 1;
            q.push(qq);
        }
    }
    return 0;
}

int main()
{
    while (scanf ("%s%d",str,&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%s",p[i][j]);
            }
        }
        scanf("%d %d %d",&sx,&sy,&sz);
        scanf("%d %d %d",&ex,&ey,&ez);
        scanf("%s",str);

        p[ex][ey][ez] = 0;

        if (bfs())
        {
            printf("%d %d\n",n,ans);
        }
        else 
            printf("NO ROUTE\n");

    }

    return 0;
}