all possible paths for the robot

Question

Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Here is the reference implementation I got, I think the implementation is wrong since it only find one path, other than all possible paths (more details, in line 10, the robot only goes down if no valid path in right. But to find all possible paths, the robot should try both right and down)? Want to confirm my understanding is correct.

ArrayList<Point> current_path = new ArrayList<Point>();
public static boolean getPaths(int x, int y) {
      Point p = new Point(x, y);
      current_path.add(p);
      if (0 == x && 0 == y) return true; // current_path
      boolean success = false;
      if (x >= 1 && is_free(x - 1, y)) { // Try right
        success = getPaths(x - 1, y); // Free! Go right
      }
      if (!success && y >= 1 && is_free(x, y - 1)) { // Try down
        success = getPaths(x, y - 1); // Free! Go down
      }
      if (!success) {
        current_path.remove(p); // Wrong way!
      }
      return success;
}

thanks in advance, Lin

Answer 1

Here's what you can do:

public  static class Point {
    int x, y;
    public Point (int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return String.format("[%d, %d]", x, y);
    }
}

public static void getPathsRec(int x, int y, Deque<Point> currentPath,
                               List<List<Point>> paths) {
    if (x == 0 && y == 0) {
        List<Point> path = new ArrayList<Point>();
        for (Point p : currentPath)
            path.add(p);
        paths.add(path);
        //System.out.println(currentPath);
        return;
    }

    if (x > 0 && is_free(x-1, y)) {
        currentPath.push(new Point(x-1, y));
        getPathsRec(x-1, y, currentPath, paths);
        currentPath.pop();
    }

    if (y > 0 && is_free(x, y-1)) {
        currentPath.push(new Point(x, y-1));
        getPathsRec(x, y-1, currentPath, paths);
        currentPath.pop();
    }
}

static int n = 2;
public static List<List<Point>> getPaths() {
    List<List<Point>> paths = new ArrayList<List<Point>>();
    Deque<Point> d = new ArrayDeque<Point>();
    d.push(new Point(n-1, n-1));
    getPathsRec(n - 1, n - 1, d, paths);
    //System.out.println(paths);
    return paths;
}

This is a simple backtracking. The idea is to visit the next state recursively but to make sure that after the call the state goes back to it's previous state(like it was before the call). Here this is done with popping the element from the Deque.

Notice that for simplicity you could introduce new class Path which would be something like:

class Path {
    List<Point> points;
}

to make the code more readable. Then getPaths() would return List<Path> which is much nicer.

Also consider redefining getPathsRec to have the signature getPathsRec(Point p, Deque<Point>, List<Path> ), that is having one argument Point instead of having x, y. Having x, y seems redundant considering the fact that you've defined class Point. Again this would make it look better.

Answer 2

Your solution is wrong because once the it reach (0 == x && y==0), the success value will always set to true. Hence, it wouldn't go into later if

Below is the sample answer for your problem. It uses backtracking algorithm:

public class test {
    static int n = 3; //substitute your n value here
    static ArrayList<Point> current_path = new ArrayList<Point>();
    static boolean[][] blockedCell = new boolean[n][n];
    public static void FindAllWay(int x, int y)
    {
        if (x <0 || y < 0) return;
        Point p = new Point(x, y);
        current_path.add(p);

        if (0 == x && 0 == y){
            System.out.println(current_path.toString());
            current_path.remove(current_path.size()-1);
            return;
        }

        if ((x > 0) && !blockedCell[x-1][y]) //go right
        {
            blockedCell[x-1][y] = true;
            FindAllWay(x-1, y);
            blockedCell[x-1][y] = false;
        }
        if ((y > 0) &&!blockedCell[x][y-1]) // go down
        {
            blockedCell[x][y-1] = true;
            FindAllWay(x, y-1);
            blockedCell[x][y-1] = false;
        }
        current_path.remove(current_path.size()-1);

    }

    public static void main(String[] args)
    {
        FindAllWay(n-1,n-1);
    }
}