Cod sursa(job #1710251)

Utilizator HealeruDaniel Guramulta Healeru Data 28 mai 2016 18:31:55
Problema Padure2 Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 1.68 kb
#include <fstream>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

const int MAX = 1000000;
const int MOD = 2000003;

int currentX{ 1 }, currentY{ 1 }, N, M, Clen;
vector<pair<int, int>> Ciuperci;
int nr;
map<pair<int, int>, int> currentPosible;

void BackT(int x, int y) {
	if (x > N || y > M) {
		return;
	}
	if (x == N && y == M) {
		nr++;
		nr %= MOD;
	}
	else {
		for (vector<pair<int, int>>::iterator it = Ciuperci.begin(); it != Ciuperci.end(); ++it) {
			if (it->first == x && it->second == y) {
				return;
			}
		}
		if (x == N) {
			BackT(x, y + 1);
			return;
		}
		if (y == M) {
			BackT(x + 1, y);
			return;
		}
		BackT(x + 1, y);
		BackT(x, y + 1);
	}
}


int isInMap(int x, int y) {
	map<pair<int,int>, int>::iterator it;
	for (it = currentPosible.begin(); it != currentPosible.end(); ++it) {
		if (it->first.first == x && it->first.second == y)
			return 1;
	}
	return 0;
}



int solve(int x, int y) {
	if (x == 1 && y == 1) {
		return 1;
	}

	if (x < 1 || y < 1) {
		return 0;
	}

	for (vector<pair<int, int>>::iterator it = Ciuperci.begin(); it != Ciuperci.end(); ++it) 
		if (it->first == x && it->second == y) {
			return 0;
		}

	if (!isInMap(x, y)) {
		currentPosible[make_pair(x, y)] = solve(x - 1, y) + solve(x, y - 1);
	}
	return currentPosible[make_pair(x, y)];

}

void read() {
	ifstream in("padure2.in");
	in >> N >> M;
	in >> Clen;
	int x, y;
	while(in>>x>>y) {
		Ciuperci.push_back(make_pair(x, y));
	}
	in.close();
}

int main() {
	read();
	BackT(1, 1);
	ofstream out("padure2.out");
	out << solve(N,M);
	//cout << solve(N, M) << endl;
	out.close();
	return 0;

}