Imagine 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.
Similar questions in Leetcode:
https://leetcode.com/problems/unique-paths/
public class Solution {
public int uniquePaths(int m, int n) {
int[][] paths = new int[m][n];
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(i == 0 && j == 0) {
paths[0][0] = 1;
} else {
paths[i][j] = (i==0 ? 0: paths[i - 1][j]) + (j ==0 ? 0: paths[i][j - 1]);
}
}
}
return paths[m - 1][n - 1];
}
}
https://leetcode.com/problems/unique-paths-ii/
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
return 0;
}
int[][] dp = new int[m][n];
dp[0][0] = 1;
for(int i = 1; i < n; ++i) {
if(obstacleGrid[0][i] == 0) {
dp[0][i] = dp[0][i - 1];
} else {
dp[0][i] = 0;
}
}
for(int i = 1; i < m; ++i) {
if(obstacleGrid[i][0] == 0) {
dp[i][0] = dp[i-1][0];
} else {
dp[i][0] = 0;
}
}
for(int i = 1; i < m; ++i) {
for(int j = 1; j < n; ++j) {
if(obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j - 1];
} else {
dp[i][j] = 0;
}
}
}
return dp[m - 1][n - 1];
}
}