题解 | #迷宫问题#给刘思光的答案3之回溯法

package m6_18;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Migong3 {
    static ArrayList<int[]> rss;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k1 = in.nextInt();
        int k2 = in.nextInt();
        int[][] data = new int[k1][k2];
        for (int i = 0; i < k1; i++) {
            for (int j = 0; j < k2; j++) {
                data[i][j] = in.nextInt();
            }
        }
        ArrayList<int[]> list = new ArrayList();
        list = fun(data, 0, 0, list, false);

        for (int[] ints : rss) {
            System.out.println("(" + ints[0] + "," + ints[1] + ")");
        }


    }
    
    //回溯寻找，即深度优先搜索
    private static ArrayList<int[]> fun(int[][] data, int x, int y, ArrayList<int[]> list, boolean back) {
        if (x == data.length - 1 && y == data[0].length - 1) {
            list.add(new int[]{x,y});
            rss=list;
            return list;
        }
        if (!back) {
            list.add(new int[]{x, y});
        }
        data[x][y] = 1;
        if (x - 1 >= 0 && data[x - 1][y] != 1) {
            fun(data, x - 1, y, list, false);
        } else if (x + 1 < data.length && data[x + 1][y] != 1) {
            fun(data, x + 1, y, list, false);
        } else if (y - 1 >= 0 && data[x][y - 1] != 1) {
            fun(data, x, y - 1, list, false);
        } else if (y + 1 < data[0].length && data[x][y + 1] != 1) {
            fun(data, x, y + 1, list, false);
        } else {
            list.remove(list.size() - 1);
            fun(data, list.get(list.size() - 1)[0], list.get(list.size() - 1)[1], list, true);
        }
        return list;
    }

}

作业：此方法含有重大bug，请刘思光同学谨慎辨别学习并修改