Cod sursa(job #284221)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 21 martie 2009 11:26:00
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

#define NMAX 153
#define mp make_pair
#define f first
#define s second
#define pb push_back

vector<pair<short int, short int> > Pd[NMAX*NMAX];
queue<pair<int,int> > q;
int C[NMAX][NMAX], M, N, Ks;
bool K[NMAX*NMAX], Viz[NMAX][NMAX];

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

int main()
{
    int x1, y1, i, j, Rez = 0, x, y, Key;

    fin >>M >>N >>Ks;

    for (i = 1; i <= M; i++)
        for (j = 1; j <= N; j++)

            fin >>C[i][j];

    x1 = Ks / N + 1;     //Init X initial, Y initial
    y1 = Ks % N;
    if (!y1) y1 = N, x1--;
    Viz[x1][y1] = 1;
    q.push(mp(x1,y1));
    while (!q.empty())
    {
        Rez++;
        x = q.front().f;           //Extragem din coada x si y
        y = q.front().s;
        q.pop();
        for (i = 0; i < 4; i++)                   //Verificam pe cele 4 coordonate daca exista cheia
        {                                         //Nu se poate iesi din matrice deoarece cheia 0 nu exista
            x1 = x + dx[i], y1 = y + dy[i];
            if (Viz[x1][y1] == 0)
            {
                if (K[C[x1][y1]])
                    q.push( mp(x1, y1));
                else
                    Pd[C[x1][y1]].pb(mp(x1,y1));
            }
            Viz[x1][y1] = 1;
        }
        
        Key = (x-1) * N + y;      //Generam cheia din camera actuala
        K[Key] = 1;

        if (!Pd[Key].empty())                            //Verificare coada pentru cheia actuala si inserare in coada Lee-ului
            for (i = 0; i < Pd[Key].size(); i++)
                q.push( mp(Pd[Key][i].f,Pd[Key][i].s));
        
    }
    fout <<Rez;
    fout.close();
    return 0;
}