Cod sursa(job #2638228)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 27 iulie 2020 15:38:01
Problema Castel Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

const int DIM = 155;

int n,m,k,stx,sty,v[DIM][DIM],nr,viz[DIM][DIM],Key[DIM*DIM],ans,Nr[DIM][DIM],c;

pair <int,int> L[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 false;
    return true;
}

void Read()
{
    fin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            nr++;
            fin>>v[i][j];
            if(nr==k)
            {
                stx=i;
                sty=j;
            }
            Nr[i][j]=nr;
        }
    }
}

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

void Lee()
{
    viz[stx][sty]=1;
    Q.push(make_pair(stx,sty));
    Key[Nr[stx][sty]]=1;
    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        ans++;
        Q.pop();
        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])
            {
                if(Key[v[i_urm][j_urm]])
                {
                    Key[Nr[i_urm][j_urm]]=1;
                    viz[i_urm][j_urm]=1;
                    Q.push(make_pair(i_urm,j_urm));
                }
                else
                    H.push(make_pair(i_urm,j_urm));
            }
        }
        if(Q.empty())
        {
            c=0;
            while(!H.empty())
            {
                int i=H.front().first;
                int j=H.front().second;
                H.pop();
                if(Key[v[i][j]] && !viz[i][j])
                {
                    viz[i][j]=1;
                    Q.push(make_pair(i,j));
                    Key[Nr[i][j]]=1;
                }
                else
                {
                    c++;
                    L[c].first=i;
                    L[c].second=j;
                }
            }
            for(int i=1;i<=c;i++)
                H.push(make_pair(L[i].first,L[i].second));
        }
    }
    fout<<ans<<'\n';
}

int main()
{
    Read();
    Lee();
}