Imagine a robot sitting on the upper left comer of an X by Ygrid. 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 Imagine certain spots are "off limits," such that the robot cannot step on them. Design an algorithm to find a path for the robot from…

CC150-9.2-Followup.java

package POJ;

public class Main{
 
	/**
	 * 
	 * Now consider if some obstacles are added to the grids. How many unique paths would there be?
	 * An obstacle and empty space is marked as 1 and 0 respectively in the grid.
	 * 
	 * 
	 */
	
	public int uniquePathsFollowup(int[][] obstacleGrid) {
		int m=obstacleGrid.length;
		int n=obstacleGrid[0].length;
		if(m==0||n==0)
			return 0;
		if(obstacleGrid[0][0]==1)
			return 0;
		int[][] result=new int[m][n];
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(obstacleGrid[i][j]==0){
					if(i==0&&j==0)
						result[i][j]=1;
					else
						result[i][j]=((i>0)?result[i-1][j]:0)+((j>0)?result[i][j-1]:0);
				}else{
					result[i][j]=0;
				}
			}
		}
		return result[m-1][n-1];
	}
}

CC150-9.2.java

package POJ;

import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
 
	/**
	 * 
	 * 9.2 Imagine a robot sitting on the upper left comer 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
	 * Imagine 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 int uniquePaths(int x, int y) {
		int[][] result = new int[x][y];
		for (int i = 0; i < x; i++) {
			result[i][0] = 1;
		}
		for (int i = 0; i < y; i++) {
			result[0][i] = 1;
		}
		for(int i=1;i<x;i++){
			for(int j=1;j<y;j++){
				result[i][j]=result[i-1][j]+result[i][j-1];
			}
		}
		return result[x-1][y-1];
	}
}