题解 | #迷宫问题#

思路：广度优先遍历矩阵。代价相同的图中，广度优先遍历可以保证遍历到的目标点就是经过最短路径到达的点。为此，我们可以创建一个Point类，属性为横纵坐标和父节点。从（0，0）出发，将经过的坐标点都设为1，避免重复经过而进入死循环。把当前点的上下左右值为0的点都加入队列中，直到遇见出口为止。遇到出口时，pos的father路径就是最短路径的逆路径。此时只需要把逆路径反转一下即可。当然我们可以利用递归可以后序输出链表的特性，省去反转路径的操作。

Java版本：

 class Point{
        int px;
        int py;
        Point father;
        Point(int px,int py,Point father){
            this.px=px;
            this.py=py;
            this.father = father;
        }
        Point(){}
    }
public  class Main{
    public static void print(Point p){
        if(p != null){
            print(p.father);
            System.out.println("("+p.px+","+p.py+")");
        }
    }
    public  static void main(String args[]){
        Scanner sc = new Scanner(System.in);
            while(sc.hasNextInt()){
            int row = sc.nextInt();
            int col = sc.nextInt();
            int [][] grid = new int[row][col];
            for(int i=0;i<row;++i){
                for(int j=0;j<col;++j){
                    grid[i][j]=sc.nextInt();
                }
            }
            Queue<Point> que = new LinkedList<Point>();
            que.offer(new Point(0,0,null));
            grid[0][0]=1;
            Point pos = null;
            while(true){
                pos = que.poll();
                int px = pos.px;
                int py = pos.py;
                if(px==row-1&&py==col-1)break;
                else {
                    if(px+1<row&&grid[px+1][py]==0){
                        grid[px+1][py]=1;
                        que.offer(new Point(px+1,py,pos));
                    }
                    if(py-1>=0&&grid[px][py-1]==0){
                        grid[px][py-1]=1;
                    	que.offer(new Point(px,py-1,pos));
                    }
                    if(px-1>=0&&grid[px-1][py]==0){
                        grid[px-1][py]=1;
                    	que.offer(new Point(px-1,py,pos)); 
                    }
                    if(py+1<col&&grid[px][py+1]==0){
                        grid[px][py+1]=1;
                    	que.offer(new Point(px,py+1,pos));
                    }
                }
            }
            print(pos);
        }
    }
}

CPP版本

#include <bits/stdc++.h>
#include <cstddef>
using namespace std;
class Pos {
    public:
        int px;
        int py;
        Pos *father;
        Pos(int px, int py, Pos *father): px(px), py(py), father(father){
        }
};
void print_road(Pos *p, Pos *q) 
{
    if(q != NULL) {
        print_road(p, q -> father);
        cout << "(" + to_string(q -> px) + "," + to_string(q -> py) + ")" << endl;
    }
}
int main() 
{
    int x, y;
    cin >> x;
    cin >> y;
    vector<vector<int>> mat;
    for(int i = 0; i < x; ++i) {
        vector<int> vec;
        for(int j = 0; j < y; ++j) {
            int temp;
            cin >> temp;
            vec.push_back(temp);
        }
        mat.push_back(vec);
    }
    queue<Pos *> que;
    Pos *p = new Pos(0, 0, NULL);
    Pos *q;
    Pos *temp;
    que.push(p);
    mat[0][0] = 1;
    while(true) {
        q = que.front();
        que.pop();
        if(q -> px == x - 1 && q ->py == y - 1) {
           print_road(p, q);
           return 0;
        } else {
            int pxa1 = q -> px + 1;
            int pxm1 = q -> px - 1;
            int pya1 = q -> py + 1;
            int pym1 = q -> py - 1;
            if(pxa1 < x && mat[pxa1][q -> py] == 0) {
                mat[pxa1][q ->py] = 1;
                temp =  new Pos(pxa1, q ->py, NULL);
                temp -> father = q;
                que.push(temp);
            }
            if(pxm1 >= 0 && mat[pxm1][q ->py] == 0) {
                mat[pxm1][q ->py] = 1;
                temp =  new Pos(pxm1, q ->py, NULL);
                 temp ->father = q;
                que.push(temp);
            }
            if(pya1 < y && mat[q ->px][pya1] == 0) {
                mat[q ->px][pya1] = 1;
                 temp = new Pos(q ->px, pya1, NULL);
                 temp ->father = q;
                que.push(temp);
            }
            if(pym1 >= 0 && mat[q ->px][pym1] == 0) {
                mat[q ->px][pym1] = 1;
                temp = new Pos(q ->px, pym1, NULL);
                 temp ->father = q;
                que.push(temp);
            }
        }
    }
    return 0;
}