Cod sursa(job #1790831)

Utilizator MoleRatFuia Mihai MoleRat Data 28 octombrie 2016 19:17:02
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
queue <int> Q;
int M,N,K;
int A[25000];
vector <int> Ls[24025];
bool u[24025];
int U[24025];
int Dir[5];
int rez;
void lee()
{
    Q.push(K);
    int x;
    u[K]=1;
    while (!Q.empty())
    {
        x=Q.front();
        Q.pop();
        if (U[x]==0)
        {
            rez++;
            U[x]=1;
        }
        for ( vector<int>::iterator it =Ls[x].begin() ; it != Ls[x].end(); ++it)
        {
            if (u[*it]==0)
            {
            u[*it]=1;
            Q.push(*it);
            }
        }
        for (int i=1; i<=4; i++)
        {
            int y=x+Dir[i];
            if (y>=1 && y<=N*M)
            {
                if (u[y]==0 && u[A[y]]==1)
                {
                    u[y]=1;
                    Q.push(y);
                }
                else
                    Ls[A[y]].push_back(y);
            }
        }
    }
}
int main()
{
    fin>>N>>M>>K;
    int nr=0;
    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=M; j++)
            fin>>A[++nr];
    }
    Dir[1]=-M;
    Dir[2]=1;
    Dir[3]=M;
    Dir[4]=-1;
    lee();
    fout<<rez<<' ';
    return 0;
}