Question9_2.java

/**
 * Imagine a robot sitting on the upper left corner of an X by Y grid.
 * The robot can only move in two directions: right and down.
 * How many possible paths are there for the robot to go from (0, 0) to (X, Y)?
 * 
 * FOLLOW UP:
 * Image certain spots are "off limits", 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.
 */

public class Question9_2 {
    /*
     * Time  Complexity: O(x*y)
     * Space Complexity: O(min(x,y))
     */
    public int numberOfPaths(int x, int y) {
        if (x < 0 || y < 0) {
            return 0;
        }
        
        if (x > y) {
            return numberOfPaths(y, x);
        }
        
        int[][] paths = new int[x + 1][2];
        for (int row = 0; row <= x; ++row) {
            paths[row][0] = 1;
        }
        paths[0][1] = 1;
        
        for (int col = 1; col <= y; ++col) {
            int currCol = col % 2;
            int prevCol = (col + 1) % 2;
            for (int row = 1; row <= x; ++row) {
                paths[row][currCol] = paths[row - 1][currCol] + paths[row][prevCol];
            }
        }
        
        return paths[x][y % 2];
    }
    

    /*
     * Time  Complexity: O(x*y)
     * Space Complexity: O(x*y)
     */
    public String path(boolean[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0 || !grid[0][0]) {
            return "Not Accessible!";
        }
        
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] accessible = new int[rows][cols];
        boolean deadCol = false;
        for (int row = 0; row < rows; ++row) {
            if (grid[row][0]) {
                accessible[row][0] = 1;
                deadCol = false;
            } else {
                break;
            }
        }
        
        for (int col = 1; !deadCol && col < cols; ++col) {
            deadCol = true;
            for (int row = 0; row < rows; ++row) {
                if (grid[row][col]) {
                    if (row - 1 >= 0 && accessible[row - 1][col] != 0) {
                        accessible[row][col] = 1;
                        deadCol = false;
                    } else if (accessible[row][col - 1] != 0) {
                        accessible[row][col] = -1;
                        deadCol = false;
                    } else {
                        accessible[row][col] = 0;
                    }
                }
            }
        }
        
        if (deadCol) {
            return "Not Accessible!";
        }
        
        StringBuffer pathBuffer = new StringBuffer();
        int row = rows - 1;
        int col = cols - 1;
        do {
            pathBuffer.insert(0, "(" + row + ", " + col + ") ");
            if (accessible[row][col] == 1) {
                --row;
            } else {
                --col;
            }
        } while (row != 0 || col != 0);
        pathBuffer.insert(0, "(0, 0) ");
        
        return pathBuffer.toString();
    }
    
    private static int factorial(int n) {
        if (n < 0) {
            return -1;
        } else if (n == 0 || n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
    
    public static void main(String[] args) {
        Question9_2 question9_2 = new Question9_2();
        
        // test cases
        for (int x = 1; x < 6; ++x) {
            for (int y = 1; y < 6; ++y) {
                System.out.println(question9_2.numberOfPaths(x, y));
                System.out.println(question9_2.numberOfPaths(x, y) - Question9_2.factorial(x + y) / (Question9_2.factorial(x) * Question9_2.factorial(y)));
                System.out.println();
            }
        }
        
        // test case for follow up
        boolean[][] grid = new boolean[3][5];
        grid[0][0] = true;
        grid[0][1] = true;
        grid[0][2] = true;
        grid[1][2] = true;
        grid[1][3] = true;
        grid[2][3] = true;
        grid[2][4] = true;
        System.out.println(question9_2.path(grid));

        System.out.println();
        grid[2][4] = true;
        System.out.println(question9_2.path(grid));
        
        System.out.println();
        grid[2][3] = false;
        System.out.println(question9_2.path(grid));
    }
}