题解 | #迷宫问题##深度遍历#

只要数据结构处理好，DFS深度遍历简单的很。

思路

这里就是一个简单的深度遍历运用。但是如何和深度遍历是个问题。 都知道，深度遍历只要触发到一个条件，便返回，可这个条件直接判断则比较麻烦。 所以，如果能把数据结构弄好，那么遍历就变得很简单。

将每个点进行图表示，每一个结点对应一个对象，同时把能访问到的下一个结点进行构造给当前对象，遍历的时候便深度遍历下一个结点，如果遍历到当前结点，其对应横纵坐标是目标点，则完成，保存数据，输出结果，

这里保存数据通过依次遍历父节点，直到父节点为空，便得到了路径，最后输出即可。

。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m=Integer.parseInt(in.next());
        int n=Integer.parseInt(in.next());
        int [][]a=new int[m][n];//一份用来保存原始数据
        int [][]b=new int[m][n];//一份用来生成图
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                a[i][j]=Integer.parseInt(in.next());//得到初始数据。
            }
        }        
        b=a.clone();
        
        Node node=new Node();
        node.Node(b,0,0);//将初始数据进行图结构化。
        
        ArrayList<int []> list=new ArrayList<>();//保存结果
        DFS(a,node,list);//深度遍历开始
        for(int j=list.size()-1;j>=0;j--){
            System.out.println("("+list.get(j)[0]+","+list.get(j)[1]+")");
        }
    }
    
    public static void DFS(int[][] a,Node node,ArrayList<int []> list){
        if(node.i==a.length-1 && node.j==a[0].length-1){
            Node node1=node;
            //开始保存结果
            list.add(new int[]{node1.i,node1.j});
            while (node1.parent!=null){
                node1=node1.parent;
                list.add(new int[]{node1.i,node1.j});
            }
            return;
        }else {
          if(node.nextup!=null){
              DFS(a,node.nextup,list);
          }
          if(node.nextdo!=null){
              DFS(a,node.nextdo,list);
          }if(node.nextle!=null){
              DFS(a,node.nextle,list);

          }if(node.nextri!=null){
              DFS(a,node.nextri,list);
          }
        }
    }
    //is方法用来判断当前坐标是否合法，如果能通则返回true，否则返回false
    public static boolean is(int s[][],int i,int j){
        if(i<0 || i>=s.length || j<0 ||j>=s[0].length){
            return false;
        }
        if(s[i][j]==1){
            return false;
        }
        return true;
    }

    static class Node{
        int i;
        int j;
        Node nextup;//指向向上的结点
        Node nextdo;//指向向下的结点
        Node nextle;//指向向左的结点
        Node nextri;//指向向右的节点
        Node parent;//指向父节点
        
        void Node(int[][] s,int i,int j){
        //构造方法，依次生成每个结点及上下左右和父亲结点。
            this.i=i;
            this.j=j;
            s[i][j]=1;
            if(is(s,i-1,j)){
                Node nodeup=new Node();
                nodeup.Node(s,i-1,j);
                nodeup.parent=this;
                this.nextup=nodeup;
            }else{
                this.nextup=null;
            }
            if(is(s,i+1,j)){
                Node nodedo=new Node();
                nodedo.Node(s,i+1,j);
                nodedo.parent=this;
                this.nextdo=nodedo;
            }else{
                this.nextdo=null;
            }
            if(is(s,i,j-1)){
                Node nodele=new Node();
                nodele.Node(s,i,j-1);
                nodele.parent=this;
                this.nextle=nodele;
            }else{
                this.nextle=null;
            }
            if(is(s,i,j+1)){
                Node noderi=new Node();
                noderi.Node(s,i,j+1);
                noderi.parent=this;
                this.nextri=noderi;
            }else{
                this.nextri=null;
            }
        }       
    }
}