矩阵行走路径有关问题
发布时间： 2013-10-21 17:02:52 作者： rapoo
矩阵行走路径问题
1、一个m*n的矩阵a[][]，机器人从左上角走到右下角，只能朝右或朝下走，输出所有路径。
2、如果矩阵有的格子可以走，有的格子不可以走，输出所有路径。(a[i][j]==1表示可以走，a[i][j]==0表示不可以走）
思路：
利用递归算法求解问题。问题1直接用深搜的思想。问题2在问题1的基础上加个判断条件即可。
关于这类题目中求解从某一点到某一点的所有可能路径的数目可参考这里
#include <iostream> #include <vector> using namespace std; struct Point { int x; int y; Point(int i, int j) : x(i), y(j) {} }; //问题1 x y是起始点，m n是终止点 向量中坐标记录路径
void Path1(int x, int y, int m, int n, vector<Point>& vec, int len) { if (x == m || y == n) return; Point p(x, y); vec[len++] = p; if (x == m - 1 && y == n - 1) { for (int i = 0; i < vec.size(); ++i) cout << vec[i].x << ' ' << vec[i].y << endl; } else { Path1(x, y+1, m, n, vec, len); Path1(x+1, y, m, n, vec, len); } } //问题2 void Path2(int x, int y, int m, int n, vector<Point>& vec, int len, int safe[][4]) { if (x == m || y == n || safe[x][y] == 0) return; Point p(x, y); vec[len++] = p; if (x == m - 1 && y == n - 1) { for (int i = 0; i < vec.size(); ++i) cout << vec[i].x << ' ' << vec[i].y << endl; } else { Path2(x, y+1, m, n, vec, len, safe); Path2(x+1, y, m, n, vec, len, safe); } } void main() { int m = 3, n = 4; int x = 0, y = 0; int len = 0; Point p(0, 0); vector<Point> vec(m+n-1, p); Path1(x, y, m, n, vec, len); int safe[][4] = { {1, 1, 1, 0},{0, 1, 1, 1}, {0, 0, 1, 1} }; Path2(x, y, m, n, vec, len, safe); }
他妹的，老想着肯定是递归，但是没想到是从小的往大的递归，老想着从高处往下！向量可以记录坐标，没必要记录走向，多了说明经过这个点的次数多！