Contents

1. 1. 题目：
2. 2. 输入：
3. 3. 输出：
4. 4. sample input：
5. 5. sample out：

• 注意：对于这种输出迷宫的最短路径考虑用BFS而不是DFS，

题目：

定义一个二维数组：

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的二维数组，表示一个迷宫。数据保证有唯一解。

输出：

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

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 out：

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

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

int mp[5][5];
int vis[5][5];

struct node{
    int x;
    int y;
    int pre;
}List[110];

int dir[4][2] = {{-1, 0}, {1 , 0}, {0, -1}, {0, 1}};//方向数组

void solve(int i){

    if(List[i].pre != -1){                          //递归从起点开始输出
        solve(List[i].pre);
        printf("(%d, %d)\n", List[i].x, List[i].y);
    }
}

void bfs(int r, int c){

    memset(vis, 0, sizeof(vis));
    int fronts = 0, rear = 1;
    int x, y, xx, yy;
    List[fronts].x = r;
    List[fronts].y = c;
    List[fronts].pre = -1;                          //起点
    vis[0][0] = 1;
    while(fronts < rear){                           //注意这里，逻辑上队列为空
        x = List[fronts].x;
        y = List[fronts].y;
        if(x == 4 && y == 4){                       //到达终点
            solve(fronts);
            return ;
        }
        for(int i = 0; i < 4; i++){
            xx = x + dir[i][0];
            yy = y + dir[i][1];
            if(!vis[xx][yy] && mp[xx][yy] == 0 && 0 <= xx && xx < 5 && 0 <= yy && yy < 5){
                vis[xx][yy] = 1;
                List[rear].x = xx;
                List[rear].y = yy;
                List[rear].pre = fronts;
                rear++;                             //逻辑上是push入队
            }
        }
        fronts++;                                   //逻辑上是pop出队
    }
}

int main(){

    freopen("input.txt", "r", stdin);
    int i, j;
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            scanf("%d", &mp[i][j]);
    printf("(0, 0)\n");
    bfs(0, 0);
    return 0;
}