Cod sursa(job #1326759)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 25 ianuarie 2015 22:18:03
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <vector>
#include <queue>
#define vint vector<int>::iterator
#define DIM 160
#define infile "castel.in"
#define outfile "castel.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

queue<int> Q;

vector<int> L[DIM * DIM];

bool keys[DIM * DIM], ok[DIM][DIM];

int a[DIM][DIM];

int n, m, k;

const int di[] = { -1, 1, 0, 0 };
const int dj[] = { 0, 0, -1, 1 };

int main() {

	f >> n >> m >> k;

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			f >> a[i][j];
			--a[i][j];
		}

	Q.push(--k);
	ok[k / m][k % m] = 1;

	int sol = 0;

	while (!Q.empty()) {
		
		++sol;
		k = Q.front();
		Q.pop();
		keys[k] = 1;

		for (vint it = L[k].begin(); it != L[k].end(); ++it) {
			if (ok[*it / m][*it % m])
				continue;
			ok[*it / m][*it % m] = 1;
			Q.push(*it);
		}

		int ic = k / m;
		int jc = k % m;

		for (int d = 0; d < 4; ++d) {
			
			int iv = ic + di[d];
			int jv = jc + dj[d];

			if (iv < 0 || iv >= n || jv < 0 || jv >= m || ok[iv][jv])
				continue;

			if (keys[a[iv][jv]]) {
				Q.push(iv*m + jv);
				ok[iv][jv] = 1;
			}
			else
				L[a[iv][jv]].push_back(iv*m + jv);
		}





	}

	g << sol;

	return 0;
}

//Trust me, I'm the Doctor!