java - 在网格算法中找到机器人的路径

Question

在通过破解编码面试做这个练习时:

a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limit" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

代码:

static int[][] MOVES = new int[][] { { 1, 0 }, { 0, 1 } };

private boolean isSafe(boolean[][] GRID, Point current) {
    if (current.row < 0 || current.row >= GRID.length 
        || current.col < 0 || current.col >= GRID[0].length 
                      || !GRID[current.row][current.col]) {
            return false;
    }
    return true;
}

/*** Check if there is a Path **/
public boolean getPath(boolean[][] grid, Point start, Point end, List<Point> path) {
    // if already reached, return true. The caller will print the path
    if (start.equals(end)) {
         return true;
    }
    // try out all the moves from the array.
    for (int i = 0; i < MOVES.length; i++) {
        int newRow = start.row + MOVES[i][0];
        int newCol = start.col + MOVES[i][1];
        Point current = new Point(newRow, newCol);
        // if it is safe to move, move forward
        if (isSafe(grid, current)) {
           // recursively try next targets and keep moving
           if (getPath(grid, current, end, path)) {
              // if the path lands up to destination, 
              // then the current position was also responsible for that,
              // hence add it to the path.
              path.add(current);
              return true;
           }
        }
    }
    return false;
}


public class Point {

    int row, col;

    public Point(int row, int col) {
        super();
        this.row = row;
        this.col = col;
    }
}

并测试:

boolean[][] GRID = new boolean[][] { 
        { true, true, true, true, true, true },
        { true, true, true, true, true, true }, 
        { true, true, true, true, true, true },
        { true, true, true, true, true, true }, 
        { true, true, true, true, true, true },
        { true, true, true, true, true, true } };

Point start = new Point(0, 0);
Point end = new Point(GRID.length - 1, GRID[0].length - 1);
List<Point> path = new ArrayList<Point>();
path.add(start);
algo.getPath(GRID, start, end, path);
System.out.println( algo.getPath(GRID, start, end, path));

我总是得到 false 作为结果。我不明白代码有什么问题。

Answer 1

这个条件永远不会为真:

if (start.equals(end)) {
    return true;
}

因为您没有在 Point 中覆盖 equals。该类继承了Object.equals的默认实现，所以 Point 的两个不同实例永远不会相等，因为在任何地方都没有逻辑来比较它们的 row 和 col 字段。