UVa 825 Walking on the Safe Side

題意：
    從左上角走到右下角，只能往右走或是往下走，有障礙的點不能走，問左上走到右下共有幾種方法？

想法：
    高中排列組合題目，dp[i][j]的方法數一定是從dp[i-1][j]和dp[i][j-1]相加而來。

	#include <iostream>
	#include <sstream>
	using namespace std;
	int main()
	{
	ios::sync_with_stdio(false);
	int T, W, N;
	cin >> T;
	while (T--) {
	cin >> W >> N;
	// Initial
	bool Map[100][100] = {0};
	int dp[100][100] = {0};
	// Input
	cin.ignore(); // ignore '\n'
	string str;
	for (int i = 1, j; i <= W; ++i) {
	getline(cin, str);
	stringstream ss(str);
	ss >> j; // ignore the first number
	while (ss >> j)
	Map[i][j] = true;
	}
	dp[1][1] = 1;
	for (int i = 1; i <= W; ++i) {
	for (int j = 1; j <= N; ++j) {
	if (Map[i][j]) continue;
	if (i > 1) dp[i][j] += dp[i-1][j];
	if (j > 1) dp[i][j] += dp[i][j-1];
	}
	}
	cout << dp[W][N] << endl;
	if (T) cout << endl;
	}
	}

view raw [UVa] 825 Walking on the Safe Side.cpp hosted with ❤ by GitHub