迷宫问题

搜索最短路 BFS

题目

信息学奥赛一本通（C++版）在线评测系统

定义一个二维数组：

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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

输入

一个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

输出

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

思路

之前的思路是用二维数组记录走到每一点所用步数, 根据BFS找到结果就退出的特性, 只存在一条路径从起点到终点满足递增, 可以像DP求方案那样逆推一遍得到。

逆推的操作可以使用DFS。

这里是把用来记录是否走过的数组bool st[][]扩展为 pair<int,int> prev[][], 即每个格子是从哪个格子走过来的。

代码

const int N = 6;
int g[N][N];
typedef pair<int, int> PII;
PII prevs[N][N];
PII q[N * N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
 
void bfs(int xx, int yy)
{
    int hh = 0, tt = 0;
    q[0] = {xx, yy};
    prevs[xx][yy] = {-1, -1};
    while (hh <= tt)
    {
        auto t = q[hh++];
        int x = t.first, y = t.second;
        if (x == 1 && y == 1)
            return;
        for (int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 1 || a > 5 || b < 1 || b > 5 || g[a][b])
                continue;
            if (prevs[a][b].first == 0 && prevs[a][b].second == 0)
            {
                q[++tt] = {a, b};
                prevs[a][b] = {x, y};
            }
        }
    }
}
 
void print_ans(int x, int y)
{
    if (x == -1 && y == -1)
        return;
    print_ans(prevs[x][y].first, prevs[x][y].second);
    printf("(%d, %d)\n", x - 1, y - 1);
}
 
int main()
{
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 5; j++)
        {
            cin >> g[i][j];
        }
    }
    bfs(5, 5);
    PII end(1, 1);
    while (true)
    {
        printf("(%d, %d)\n", end.first - 1, end.second - 1);
        if (end.first == 5 && end.second == 5)
            break;
        end = prevs[end.first][end.second];
    }
    return 0;
}