华为OD机试真题 - 园区参观路径

    static int[][] DISTANCE = {{1,0}, {0,1}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] mn = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][] map = new int[mn[0]][mn[1]];
        for (int i = 0; i < mn[0]; i++) {
            for (int j = 0; j < mn[1]; j++) {
                map[i][j] = in.nextInt();
            }
        }
        List pathList = new ArrayList<>();
        String path = &quot;&quot;;
        dfs(map, path, pathList, 0, 0, mn);
        System.out.println(pathList.size());
    }

    public static void dfs(int[][] map, String path, List pathList, int i, int j, int[] mn) {
        if (path.endsWith(&quot;&quot; + (mn[0] - 1) + &quot;&quot; + (mn[1] - 1)) &amp;&amp; !pathList.contains(path)) {
            pathList.add(path);
            return;
        }
        if (i > map.length - 1 || i < 0 || j > map.length - 1 || j < 0)
            return;
        if (map[i][j] == 1)
            return;
        for (int k = 0; k < DISTANCE.length; k++) {
            dfs(map, path + i + j, pathList, i + DISTANCE[k][0], j + DISTANCE[k][1], mn);
        }
    }