学步园

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
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);
}