Cod sursa(job #520226)

Utilizator darrenRares Buhai darren Data 7 ianuarie 2011 16:05:34
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int D1[] = {0, 1, 0, -1},
          D2[] = {1, 0, -1, 0};

void Fill(int posx, int posy);

int N, M, K;
int V[152][152], enter = 1;
bool Key[22502], InQueue[22502], S[152][152], Open[152][152];
vector<pair<int, int> > Where[150 * 150 + 1];
queue<int> Q;

int getCod(int x, int y)
{
	return (x - 1) * M + y;
}
pair<int, int> getCoord(int cod)
{
	int x = (cod % M == 0 ? cod / M : cod / M + 1);
	cod -= (x - 1) * M;
	return make_pair(x, cod);
}

int main()
{
	ifstream fin("castel.in");
	ofstream fout("castel.out");

	fin >> N >> M >> K;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
		{
			fin >> V[i][j];
			Where[V[i][j]].push_back(make_pair(i, j));
		}

	pair<int, int> coord = getCoord(K);
	S[coord.first][coord.second] = true;
	Open[coord.first][coord.second] = true;
	Key[K] = true;

	Q.push(K);
	while (!Q.empty())
	{
		int now = Q.front(); Q.pop();
		for (vector<pair<int, int> >::iterator it = Where[now].begin(); it != Where[now].end(); ++it)
        {
            Open[it->first][it->second] = true;
            for (int k = 0; k < 4; ++k)
            {
                int nowx = it->first + D1[k];
                int nowy = it->second + D2[k];

                if (S[nowx][nowy])
                {
                    Fill(it->first, it->second);
                    break;
                }
            }
        }
	}

	fout << enter;

	fin.close();
	fout.close();
}

void Fill(int posx, int posy)
{
    if (!Open[posx][posy] || S[posx][posy] || posx < 1 || posy < 1 || posx > N || posy > M) return;

    if (!Key[getCod(posx, posy)])
    {
        Q.push(getCod(posx, posy));
        Key[getCod(posx, posy)] = true;
    }
    S[posx][posy] = true;
    ++enter;

    Fill(posx + 1, posy);
    Fill(posx - 1, posy);
    Fill(posx, posy + 1);
    Fill(posx, posy - 1);
}