寻找迷宫的出口

Question

我为 Coursera 上关于图形的课程中给出的编程作业编写了这段代码。在此处输入代码。它通过了问题描述中给出的测试用例，但在提交时失败了一个我是图表的新手。谁能帮我找出这段代码中的错误？

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Iterator;

public class Reachability {

    private static boolean[] visited;

    private static int reach(ArrayList<Integer>[] adj, int x, int y) {
        if(x == y){
            return 1;
        }
        
        visited[x] = true;
        Iterator itr = adj[x].iterator();
        while(itr.hasNext()){
            x = (int)itr.next();
            if(!visited[x]){
                return reach(adj,x,y);
            }
        }
        return 0;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            x = scanner.nextInt();
            y = scanner.nextInt();
            adj[x - 1].add(y - 1);
            adj[y - 1].add(x - 1);
        }
        int x = scanner.nextInt() - 1;
        int y = scanner.nextInt() - 1;
        visited = new boolean[n];
        System.out.println(reach(adj, x, y));
    }
}

下面是失败的测试用例。

失败案例 #6/16：（错误答案）

输入： 100 100 27 96 6 9 81 98 21 94 22 68 76 100 8 50 38 86 71 75 32 93 16 50 71 84 6 72 22 58 7 19 19 76 44 75 24 76 31 35 11 89 42 98 63 92 37 38 20 98 45 91 23 53 37 91 76 93 67 90 12 22 43 52 23 56 67 68 1 21 17 83 63 72 30 32 7 91 50 69 38 44 55 89 15 23 11 72 28 42 22 69 56 79 5 83 55 73 13 72 7 93 20 54 21 55 66 89 2 91 18 88 26 64 11 61 28 59 12 86 42 95 17 82 50 66 66 99 40 71 20 40 5 66 92 95 32 46 7 36 44 94 6 31 19 67 26 57 53 84 10 68 28 74 34 94 25 61 71 88 10 89 28 52 72 79 39 73 11 80 44 79 13 77 30 96 30 53 10 39 1 90 40 91 62 71 44 54 15 17 69 74 13 67 24 69 34 96 21 50 20 91 42 46

你的输出： 0

正确输出： 1

Answer 1

问题是，如果 y 无法通过 first 未访问的邻居到达 reach()，那么您会提前 return =14=]:

return reach(adj,x,y);

你想做的是：

如果可以达到y那么return1.
如果无法到达 y 则继续下一个邻居

那将是：

if (reach(adj, x, y) == 1)
  return 1;

不相关的评论：您可能想使用 Iterator<Integer> 而不是原始类型 Integer。这避免了转换和编译器警告。

寻找迷宫的出口

Finding exit from a maze

java

graph-theory

maze