Cod sursa(job #2522275)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 12 ianuarie 2020 11:39:44
Problema Castel Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

const int DIM = 155;

#define mp make_pair
#define x first
#define y second

int v[DIM][DIM],P[DIM][DIM],Key[DIM*DIM],n,m,k,nr,sx,sy,ans=0,IsOk;

bool viz[DIM][DIM],InQueue[DIM*DIM];

int dl[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};

bool OK(int i, int j)
{
    if(i<1 || j<1 || i>n || j>m)
        return 0;
    return 1;
}

void Read()
{
    fin>>n>>m>>k;
    nr=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            fin>>v[i][j];
            nr++;
            P[i][j]=nr;
            if(nr==k)
            {
                sx=i;
                sy=j;
            }
        }
    }
}

queue < pair<int,int> > Q;
queue < pair<int,int> > H;

void Fill()
{
    IsOk=0;
    Q.push(mp(sx,sy));
    Key[v[sx][sy]]=1;
    viz[sx][sy]=1;
    while(!Q.empty())
    {
        int i=Q.front().x;
        int j=Q.front().y;
        if(Key[v[i][j]])
        {
            IsOk=1;
            ans++;
            Key[P[i][j]]=1;
            for(int dir=0;dir<4;dir++)
            {
                int i_urm=i+dl[dir];
                int j_urm=j+dc[dir];
                if(OK(i_urm,j_urm) && !viz[i_urm][j_urm])
                {
                    Q.push(mp(i_urm,j_urm));
                    viz[i_urm][j_urm]=1;
                }
            }
        }
        else
        {
            if(!InQueue[P[i][j]])
            {
                H.push(mp(i,j));
                InQueue[P[i][j]]=1;
            }
        }
        Q.pop();
        if(Q.empty())
        {
            if(!IsOk)
                break;
            else
            {
                IsOk=0;
                while(!H.empty())
                {
                    int a=H.front().x;
                    int b=H.front().y;
                    InQueue[P[a][b]]=0;
                    Q.push(mp(a,b));
                    H.pop();
                }
            }
        }
    }
}

int main()
{
    Read();
    Fill();
    fout<<ans<<'\n';
}