CC150 9.2

9_2.cpp

/* CC150 9.2 */

#include <iostream>
#include <set>

using namespace std;

int gridPaths(int x, int y)
{
	if (x == 0 || y == 0)
		return 1;
	int **count = new int*[x+1];
	for (int i = 0; i <= x; ++i) {
		count[i] = new int[y+1];
		for (int j = 0; j <= y; ++j) {
			if (i == 0) // i == 0
				count[i][j] = 1;
			else if (j == 0) // i !=0, j == 0
				count[i][j] = 1;
			else // i != 0, j != 0
				count[i][j] = count[i - 1][j] + count[i][j - 1];
		}
	}
	return count[x][y];
}

int gridPathsSimple(int x, int y)
{
	int fact = 1;
	int factX = 1, factY = 1;
	for (int i = 1; i <= x + y; ++i) {
		fact *= i;
		if (i == x)
			factX = fact;
		if (i == y)
			factY = fact;
	}
	return fact / (factX * factY);
}

int gridPaths(int x, int y, set<pair<int, int>> offLimitSpots)
{
	if (x == 0 || y == 0)
		return 1;
	int **count = new int*[x + 1];
	for (int i = 0; i <= x; ++i) {
		count[i] = new int[y + 1];
		for (int j = 0; j <= y; ++j) {
			if (offLimitSpots.find(make_pair(i, j)) != offLimitSpots.end())
				count[i][j] = 0;
			else if (i == 0)
				count[i][j] = 1;
			else if (j == 0)
				count[i][j] = 1;
			else
				count[i][j] = count[i - 1][j] + count[i][j - 1];
		}
	}
	return count[x][y];
}

int main()
{
	int x, y;
	cin >> x >> y;
	cout << gridPathsSimple(x, y) << endl;
	cout << gridPaths(x, y) << " possible paths from (0, 0) to (" << x << ", " << y << ")" << endl;
	set<pair<int, int>> offLimitSpots;
	int i, j;
	while (cin >> i >> j) {
		if (i < 0 || i > x || j < 0 || j > y)
			cerr << "Invalid point! Input again..." << endl;
		offLimitSpots.insert(make_pair(i, j));
	}
	cout << gridPaths(x, y, offLimitSpots) << " possible paths with off limits spots" << endl;
	return 0;
}