Cod sursa(job #1151963)

Utilizator irimiecIrimie Catalin irimiec Data 24 martie 2014 14:30:14
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

int n, m, k, qx, qy, res, in[151][151], viz[151][151], key[151*151];
deque<int> Q;
vector<int> lst[151*151];

int dx[4] = {-1, 1,  0, 0};
int dy[4] = { 0, 0, -1, 1};

void read()
{
	f >> n >> m >> k;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			f >> in[i][j], in[i][j]--;
}

void solve()
{
	int x;
	res = 0;
	Q.push_back(--k);
	viz[k/m][k%m] = 1;
	while(Q.size() > 0)
	{
		x = Q.front();
		Q.pop_front();
		key[x] = 1;
		++res;
		for(int i = 0; i < (int)lst[x].size(); ++i)
		{
			if(!viz[lst[x][i]/m][lst[x][i]%m])
			{
				viz[lst[x][i]/m][lst[x][i]%m] = 1;
				Q.push_back(lst[x][i]);
			}
		}
		for(int i = 0; i < 4; ++i)
		{
			qx = x/m + dx[i];
			qy = x%m + dy[i];
			if(qx < 0 || qy < 0 || qx >= n || qy >= m || viz[qx][qy])
				continue;
			if(key[in[qx][qy]])
			{
				Q.push_back(qx*m+qy);
				viz[qx][qy] = 1;
			}
			else
			{
				lst[in[qx][qy]].push_back(qx*m + qy);
			}
		}
	}
}

int main()
{
	read();
	solve();
	g << res << '\n';
}