poj3984 迷宫问题

题目：

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)

题意很简单，其实可以用广搜。
问题在于如何模拟最短路径，其实我们可以在结构体队列中设一个记录方向数组，这个数组中的元素记录从 上个点到这个点需要通过什么方式（上下左右，因为为了广搜，我们设了方向数组，用下标代表上下左右），没走一步记录一次。

参考代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int mp[6][6];
bool vis[6][6];
int sx = 0, sy = 0, ex = 4, ey = 4;
int dx[4] = {-1, 1, 0, 0};//上下左右;
int dy[4] = {0, 0, -1, 1};
struct node {
    int x, y;
    int steps;
    int pt[30];//记录从上一步到这一步需往哪里走;
} que[30];

void input() {
    for (int i = 0;i < 5;++i) {
        for (int j = 0;j < 5;++j) {
            cin >> mp[i][j];
        }
    }
    memset(vis, false, sizeof(vis));
}

void bfs() {
    node s;
    s.x = sx;
    s.y = sy;
    s.steps = 0;
    s.pt[s.steps] = 0;//还在起点;
    int l = 0, r = 0;
    que[r++] = s;
    vis[sx][sy] = true;
    node p;
    while (l != r) {//队列不为空;
        p = que[l++];
        if (p.x == ex && p.y == ey) {
            int xx = 0, yy = 0;
            cout << "(" << xx << ", " << yy << ")" << endl;
            for (int i = 1;i <= p.steps;++i) {
                 xx = xx + dx[p.pt[i]];
                 yy = yy + dy[p.pt[i]];
                //cout << "............" << dx[p.pt[i]] << endl;
                //cout << xx << " " << yy << endl;
                cout << "(" << xx << ", " << yy << ")" << endl;
            }
            return;
        }
        node q;
        for (int i = 0;i < 4;++i) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && mp[nx][ny] != 1 && !vis[nx][ny]) {
                q.x = nx;
                q.y = ny;
                q.steps = p.steps + 1;
                ////////////////
                for (int j = 0;j < p.steps;++j) {
                    q.pt[j] = p.pt[j];//将之前的路径复制下来;
                }
                q.pt[q.steps] = i;//从p点到q点需要怎么走;//i = 0 : 上, i = 1 : 下, i = 2 : 左, i = 3 : 右;
                que[r++] = q;
                vis[nx][ny] = true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    bfs();
    return 0;
}

转载于:https://www.jianshu.com/p/82e0f3f7dcab