POJ3984-迷宫问题【BFS】

定义一个二维数组：

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

思路：广搜问题，关键是要在访问的同时记录路径，以便输出路径。

#include <iostream>

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <string>

#include <queue>

using namespace std;

int a[6][6],d[10][10],vis[6][6];

struct node

{

    int r,c;

};

queue <node> que;

node father[10][10];    //记录父节点，方便打印

int dx[4]={0,0,1,-1};

int dy[4]={1,-1,0,0};

vector<node> nodes;     //记录路径

void print(node u)

{

    while(1)

    {

        nodes.push_back(u);  //尾部加入元素

        if(d[u.r][u.c]==0)

            break;            //头结点

        u=father[u.r][u.c];

    }

    for(int i=nodes.size()-1;i>=0;--i)

        printf("(%d, %d)\n",nodes[i].r,nodes[i].c);

}

void bfs()

{

    node zero;

    zero.c=0,zero.r=0;

    d[0][0]=0,vis[0][0]=1;

    que.push(zero);

    while(!que.empty())

    {

        node front=que.front();

        que.pop();

        if(front.r==4 && front.c==4)

        {

            print(front);

            return;

        }

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

        {

            int x=front.r+dx[i];           //分别向上下左右访问

            int y=front.c+dy[i];

            node v;

            v.r=x,v.c=y;

            if(x>=0 && x<5 && y>=0 && y<5 && a[x][y]==0 && !vis[x][y])

            {

                d[x][y]=d[front.r][front.c]+1;   //记录层数

                father[x][y]=front;              //记录父节点

                vis[x][y]=1;                     //标记节点已经访问

                que.push(v);                     //插入队列

            }

        }

    }

}

int main()

{

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

        for(int j=0;j<5;++j)

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

    bfs();

}

巴特西

POJ3984-迷宫问题【BFS】

最新文章

热门文章