CODEWITHSUNDEEP
javaalgorithmmultidimensional-array
SarahData
SarahData

Reputation: 809

Find a path of robot in a grid algorithm

While doing this exercice from cracking the coding interview:

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.

Code:

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;
    }
}

And to test:

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));

I always get false as a result. I don't understand what's wrong with the code.

Upvotes: 1

Views: 1686

Answers (1)

janos
janos

Reputation: 124648

This condition will never be true:

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

Because you did not override equals in Point. The class inherits the default implementation of Object.equals, and so two distinct instances of Point will never be equal, because there is no logic anywhere to compare their row and col fields.

Upvotes: 1

Related Questions