Cod sursa(job #930635)

Utilizator tudorv96Tudor Varan tudorv96 Data 27 martie 2013 19:14:26
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 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 <short> Q;
vector <short> K[MAX*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] = 1;
	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] = 1;
				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();
	}
	ofstream fout (out);
	fout << sol;
	fout.close();
	return 0;
}