首页 > 其他 > 详细

迷宫问题

时间:2018-09-22 21:02:50      阅读:181      评论:0      收藏:0      [点我收藏+]

迷宫问题(基本BFS+保存路径)

题目链接:POJ 3984

Description

定义一个二维数组:

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

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

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

题解:

本题是基本的BFS搜索寻求最短路,然后要去输出最短路径。输出最短路径可以用一个数组保存每一个的前一个位置,也可以直接在结构体中多定义一个变量pre,作为每一个点的前驱,定义一个自己的队列。下面两份代码都给出。

代码:

数组保存

#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<cctype>
#include<string>
#include<cmath>
#include<iomanip>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
int num[6][6];
int vis[6][6];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
struct  Point
{
    int x, y;
}temp1,temp2;
Point pre[10][10];
Point ans[30];
queue<Point>q;

int main()
{
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> num[i][j];
    temp1.x = 0, temp2.x = 0;
    vis[0][0] = 1;
    q.push(temp1);
    while (!q.empty())
    {
        temp1 = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            temp2.x = temp1.x + dx[i], temp2.y =temp1.y + dy[i];
            if (temp2.x >=0 && temp2.y >=0 && temp2.x< 5&&temp2.y < 5 &&!vis[temp2.x][temp2.y]&&num[temp2.x][temp2.y]==0)
            {
                q.push(temp2);
                vis[temp2.x][temp2.y] = vis[temp1.x][temp1.y] + 1;
                pre[temp2.x][temp2.y].x = temp1.x;//保存前一个位置的横坐标
                pre[temp2.x][temp2.y].y = temp1.y;
            }
        
        }
        if (vis[4][4])break;
    }
    int lastx = 4, lasty = 4;
    int x1,y1, num = 0;
    while (lastx||lasty)
    {
        ans[num].x = lastx;
        ans[num++].y = lasty;
        x1 = lastx;
        y1 = lasty;
        lastx = pre[x1][y1].x;
        lasty = pre[x1][y1].y;
    }
    printf("(0, 0)\n");
    for (int i = num - 1; i >= 0; i--)
        printf("(%d, %d)\n", ans[i].x, ans[i].y);
    return 0;
}

结构体保存

#include<iostream>
#include<cstring>
using namespace std;
int maze[5][5];
int vis[5][5];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
//不能用stl里面的队列,因为会删除节点,现在只定义一个队列,维护头尾指针即可,指针的移动代表删除添加
struct quequ {
    int x, y, pre;
}q[100];
void output(int  cur)
{
    if (q[cur].pre != -1)
        output(q[cur].pre);
        cout << "(" << q[cur].x << ", " << q[cur].y << ")" << endl;
}
void BFS()
{
    int front, rear;
    q[front = rear = 0].x = 0;
    q[front].y = 0;
    q[rear++].pre = -1;
    vis[0][0] = 1;
    while (front<rear)
    {
        for (int i = 0; i < 4; i++)
        {
            int x = q[front].x + dx[i];
            int y = q[front].y + dy[i];
            if (maze[x][y] == 0 && !vis[x][y] && x >= 0 && x < 5 && y >= 0 && y < 5)
            {
                vis[x][y] = 1;
                q[rear].x= x;
                q[rear].pre = front;
                q[rear++].y = y;
            }
            if (x == 4 && y == 4)
            {
                output(front);
                cout << "(" << x << ", " << y << ")" << endl;
                return;
            }
        }
        front++;
    }
}
int main()
{
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> maze[i][j];
    BFS();
    return 0;
}

迷宫问题

原文:https://www.cnblogs.com/gzr2018/p/9691028.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!