题解 | #迷宫问题#

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

Java版本：

import java.util.*;
 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 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));
                    }
                }
            }
            Stack<Point> stack = new Stack<Point>();
                while(pos!=null){
                stack.push(pos);
                pos=pos.father;
            }
            while(!stack.isEmpty()){
                Point temp = stack.peek();
                stack.pop();
                System.out.println("("+temp.px+","+temp.py+")");
            }
        }
    }
}

利用递归可以后序输出链表的特性，可以省去反转路径的操作：

 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);
        }
    }
}