Coding Interview 8.2

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