java - 递归回溯二维数组（水会从地图上掉下来）

Question

我正在尝试解决递归回溯问题，其中我们必须从二维整数数组中的给定坐标开始，并找到到数组边缘单元的路径，使得沿路径的每个连续元素小于或等于到前一个（从给定元素开始）如果当前单元格中的元素等于前一个元素，我不知道如何正确回溯，所以我只使用每个单元格中具有不同值的测试用例。任何帮助/评论将不胜感激这是我到目前为止的代码：

public static boolean canFlowOffMap(int[][] map, int row, int col) {
    int current = map[row][col];
    return mthd6(map, current, row, col, false);
}

private static int[][] OPTIONS = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

private static boolean mthd6(int[][] map, int current, int r, int c, boolean result) {
    if (r == 0 || c == 0 || r == map.length -1 || c == map[0].length -1) {
        return true;
    } else {
        for (int[] option : OPTIONS) {
            r += option[0];
            c += option[1];
            if (map[r][c] < current) {
                current = map[r][c];
                result = mthd6(map, current, r, c, false);
            }
            r -= option[0];
            c -= option[1];
        }
        return result; 
    }
}

标签： javarecursiondata-structuresrecursive-backtracking

Answer 1

请参阅我上面的评论，并添加一个跟踪您已经访问过的点的地图（因为没有再去那里的意义）。

private static boolean mthd6(int[][] map, int r, int c, List<Point> visited) {
  int current = map[row][col];
  visited.add(new Point(r, c));
  if (r == 0 || c == 0 || r == map.length -1 || c == map[0].length -1) {
    return true;
  } else {
    for (int[] option : OPTIONS) {
        r += option[0];
        c += option[1];
        if (!visited.contains(new Point(r, c) && map[r][c] <= current) {
            result = result || mthd6(map, r, c);
        }
        r -= option[0];
        c -= option[1];
    }
    return result; 
  }
}