c******t
发帖数: 1500 | 1 就是那道经典的
count paths in a matrix with obsticles
如果仅仅是count paths in a matrix,那么很简单的DP就解决了。下面是我写的C++代
码，在VS2008下调试通过：
int path(int start_x, int start_y, int end_x, int end_y)
{
if(start_x == end_x || start_y == end_y)
{
return 1;
}
return path(start_x + 1, start_y, end_x, end_y) + path(start_x, start_y
+ 1, end_x, end_y);
}
可是如果矩阵里面有障碍的话，我就不知道该怎么解决了
还请版里的各位达人赐教，多谢了！ | g***s
发帖数: 3811 | 2 your codes are not DP. O(2^n)
you need store the visited nodes. | d**e
发帖数: 6098 | 3 please refer here
http://www.ihas1337code.com/2010/11/unique-paths.html
it should be similar. but you have to define what value in the cell stands
for obstacle and then add the checking. assume that all cells are non-
negative and 0 is obsacle.
int path(int [][] matrix, int m, int n){
matrix[m-1][n-1] = 1;
for(int r = m - 1; r >= 0; r--){
for(int c = n - 1; c >= 0; c--){
if(r == m - 1 && c == n - 1)
continue;
if(matrix[r][c] != 0)
matrix[r][c] = matrix[r+1][c] + matrix[r][c+1];
}
}
return matrix[0][0];
}
【在 c******t 的大作中提到】
: 就是那道经典的
: count paths in a matrix with obsticles
: 如果仅仅是count paths in a matrix,那么很简单的DP就解决了。下面是我写的C++代
: 码，在VS2008下调试通过：
: int path(int start_x, int start_y, int end_x, int end_y)
: {
: if(start_x == end_x || start_y == end_y)
: {
: return 1;
: }
|
|
