a********r
发帖数: 218 | 1 print all possible path in m*n matrix, you can proceed only if you meet 1
e.g.
1 1 1
0 1 1
0 0 1
the output shall be
path1: [00, 01, 02, 12, 22] (e.g. 22 means row 2, col 2)
path2: [00, 01, 11, 12, 22]
那位大牛能贡献一下c/c++ code, thanks! | Z**********4
发帖数: 528 | 2 vector > matrixPath(vector > matrix){
vector > paths;
int m = matrix.size();
if(m==0) return paths;
int n = matrix[0].size();
if(n==0) return paths;
vector solution;
getPath(matrix, paths, 0, 0, solution, m, n);
return paths;
}
void getPath(vector >& matrix, vector >& paths,
int i, int j, vector solution, int m, int n){
if(i==m-1 && j==n-1){
solution.push_back(indexToString(i, j));
paths.push_back(solution);
solution.pop_back();
return;
}
if(i
solution.push_back(indexToString(i, j));
getPath(matrix, paths, i+1, j, solution, m, n);
solution.pop_back();
}
if(j
solution.push_back(indexToString(i, j));
getPath(matrix, paths, i, j+1, solution, m, n);
solution.pop_back();
}
}
// Utilility
string indexToString(int i, int j); | Z**********4
发帖数: 528 | | e*******i
发帖数: 56 | 4 The last solution has a bug, it will loop forever.
Following is tested to work.
/*****************************************/
int A[4][4]={
{1,1,1,1},
{0,1,1,1},
{0,1,1,1},
{0,0,0,1}
};
struct Delta
{
int dx;
int dy;
};
Delta d[4]={
{0,1}, {1,0}, {-1, 0}, {0,-1} };
void dfs(vector< pair > &edgeTo, int *A, int m, int n, int i, int
j)
{
if( i>=m || j>=n || *(A+i*m+j)!=1 ) return;
edgeTo.push_back( pair(i, j) );
*(A+i*m+j)=2; //mark as visited
if(i==m-1 && j==n-1 )
{
for(int k=0; k
cout<
cout<
}
for(int k=0;k<4;k++)
dfs(edgeTo, A, m, n, i+d[k].dx, j+d[k].dy);
if(!edgeTo.empty() )
{
pair p=edgeTo.back();
*(A+p.first*m+p.second)=1;
edgeTo.pop_back();
}
}
void allPath(int *A, int m, int n)
{
vector< pair > edgeTo;
dfs(edgeTo, A, 4, 4, 0, 0);
}
int main()
{
allPath(&A[0][0], 3, 3);
} | Z**********4
发帖数: 528 | 5 题目条件没说清楚。
我assume只能往下或者往右走。
上面是可以四个方向都可以走，那就需要标记。 | a********r
发帖数: 218 | 6 Zhuimeng1314大牛：
why do we need to
"solution.pop_back();"
after each backtrack?
I am 菜鸟，don't really understand recursion, can you explain it in plain
text? | Z**********4
发帖数: 528 | 7 不是大牛。。
push_back的意思就是把当前点加入路径当中。
然后递归调用，进行下一个点的判断。
至于为什么要pop出去是因为递归就是这样的，因为每次有很多种可能，当你选择一种
可能进行计算之后，必须
记得还原当前的改动，回到做出选择之前的状态，然后再选择另外的可能。
【在 a********r 的大作中提到】
: Zhuimeng1314大牛：
: why do we need to
: "solution.pop_back();"
: after each backtrack?
: I am 菜鸟，don't really understand recursion, can you explain it in plain
: text?
|
|
