题解 | 迷宫问题

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
           int row = scanner.nextInt();
           int column = scanner.nextInt();
           int[][] vals = new int[row][column];
           List<Integer> rows = new ArrayList<>();
           List<Integer> columns = new ArrayList<>();
           for(int i = 0; i < row; i ++)
           {
               for(int j = 0; j < column; j ++)
               {
                   vals[i][j] = scanner.nextInt();
               }
           }
           dfs(vals,0,0,rows,columns);
           for(int i = 0; i < rows.size(); i ++)
           {
               System.out.println("("  +rows.get(i) + "," + columns.get(i) + ")");
           }
        }
    }
     public static boolean dfs(int[][] vals,int row,int column,List<Integer> rows,List<Integer> columns)
    {
        rows.add(row);
        columns.add(column);
        vals[row][column] = 1;
        if(row == vals.length - 1 && column == vals[0].length - 1)
        {
            return true;
        }
        //向上走
        if(row - 1 >= 0 &&
        vals[row -1][column] == 0 &&
        dfs(vals,row - 1,column,rows,columns))
        {
             return true;
        }
        //向右走
        if(column + 1 < vals[0].length &&
                vals[row][column + 1] == 0 &&
                dfs(vals,row,column + 1,rows,columns))
        {
            return true;
        }

        //向下走
        if(row + 1 < vals.length &&
                vals[row + 1][column] == 0 &&
                dfs(vals,row + 1,column,rows,columns))
        {
            return true;
        }

        //向左走
        if(column - 1 >= 0 &&
                vals[row][column - 1] == 0 &&
                dfs(vals,row,column - 1,rows,columns))
        {
            return true;
        }
        //走到这儿说明此路不通
        rows.remove(rows.size() - 1);
        columns.remove(columns.size() - 1);
        return false;
    }
}