f*********m
发帖数: 726 | 1 A robot is located at the top-left corner of a m x n grid (marked ‘Start’
in the diagram below). The robot can only move either down or right at any
point in time. The robot is trying to reach the bottom-right corner of the
grid (marked ‘Finish’ in the diagram below). How many possible unique
paths are there?
Follow up for "Unique Paths":
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.
我修改了一下leetcode的答案，不知对否？谢谢。
注：m和n是grid的size.
1.Recursive方法：
int backtrack(int r, int c, int m, int n, vector >& grid) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;
if (grid[r+1][c] == 0 && grid[r][c+1] == 0)
return backtrack(r+1, c, m, n, grid) + backtrack(r, c+1, m, n, grid);
else if (grid[r+1][c] == 1 && grid[r][c+1] == 0)
return backtrack(r, c+1, m, n, grid);
else if (grid[r+1][c] == 0 && grid[r][c+1] == 1)
return backtrack(r+1, c, m, n, grid);
else
return 0;
}
2. DP (top->down):
const int M_MAX = 100;
const int N_MAX = 100;
int backtrack(vector >&grid, int r, int c, int m, int n, int mat
[][N_MAX+2]) {
if (r == m && c == n)
return 1;
if (r > m || c > n)
return 0;
if (mat[r+1][c] == -1 && grid[r+1][c] == 0)
mat[r+1][c] = backtrack(grid,r+1, c, m, n, mat);
else if (mat[r+1][c] == -1 && grid[r+1][c] == 1)
mat[r+1][c] = 0;
if (mat[r][c+1] == -1 && grid[r][c+1] == 0)
mat[r][c+1] = backtrack(grid,r, c+1, m, n, mat);
else if (mat[r+1][c] == -1 && grid[r][c+1] == 1)
mat[r][c+1] = 0;
return mat[r+1][c] + mat[r][c+1];
}
int bt(vector >&grid, int m, int n) {
int mat[M_MAX+2][N_MAX+2];
for (int i = 0; i < M_MAX+2; i++) {
for (int j = 0; j < N_MAX+2; j++) {
mat[i][j] = -1;
}
}
return backtrack(grid,1, 1, m, n, mat);
}
3. DP 2 (bottom->up):
const int M_MAX = 100;
const int N_MAX = 100;
int dp(vector >&grid, int m, int n) {
int mat[M_MAX+2][N_MAX+2] = {0};
mat[m][n+1] = 1;
for (int r = m; r >= 1; r--)
for (int c = n; c >= 1; c--){
int t = 0;
if (grid[r+1][c] == 0)
t = t+mat[r+1][c];
if (grid[r][c+1] == 0)
t = t+mat[r][c+1];
mat[r][c] = t;
}
return mat[1][1];
} | c*******r
发帖数: 610 | |
|
