Cod sursa(job #930610)

Utilizator tudorv96Tudor Varan tudorv96 Data 27 martie 2013 19:02:25
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

#define in "castel.in"
#define out "castel.out"
#define MAX 155

short n, m, k, v[MAX][MAX], sol;
bool a[MAX][MAX], key[MAX*MAX];

const short dx[] = {1, 0, -1, 0},
			dy[] = {0, 1, 0, -1};

queue <int> Q;
vector <int> K[MAX];

int main ()
{
	ifstream fin (in);
	fin >> m >> n >> k;
	Q.push (--k);
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j) {
			fin >> v[i][j];
			v[i][j]--;
		}
	a[k / n][k % n] = true;
	fin.close();
	while (Q.size()) {
		int f = Q.front();
		key[f] = true;
		sol++;
		for (unsigned i = 0; i < K[f].size(); ++i)
			if (!a[K[f][i] / n][K[f][i] % n]) {
				a[K[f][i] / n][K[f][i] % n] = true;
				Q.push (K[f][i]);
			}
		for (int k = 0; k < 4; ++k) {
			int ii = f / n + dx[k];
			int jj = f % n + dy[k];
			if (ii >= 0 && jj >= 0 && ii < m && jj < n && !a[ii][jj]) {
				if (key[v[ii][jj]]) {
					Q.push (ii * n + jj);
					a[ii][jj] = true;
				}
				else
					K[v[ii][jj]].push_back (ii * n + jj);
			}
		}
		Q.pop();
	}
	/*for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j)
			cout << a[i][j] << " ";
		cout << "\n";
	}
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j)
			cout << key[i * n + j] << " ";
		cout << "\n";
	}*/
	ofstream fout (out);
	fout << sol;
	fout.close();
	return 0;
}