Cod sursa(job #2006233)

Utilizator sergiudnyTritean Sergiu sergiudny Data 28 iulie 2017 23:53:37
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>
#define DM 152
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");

unordered_set<int>key;
bitset<DM>viz[DM],inQueue[DM];
deque<pii>Q;
int mt[DM][DM],n,m,k,ans,timp=1;
int di[]={1,0,-1,0};
int dj[]={0,1,0,-1};

bool isGood(int i,int j){
    return i && j && i<=n && j<=m;
}

int main()
{
    fin>>n>>m>>k;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
        fin>>mt[i][j];

    int i1=k/n+1,j1=k%m+m*(k%m==0);
    Q.push_front({i1,j1});
    viz[i1][j1]=1,inQueue[i1][j1]=1;
    key.insert(k);

    while(1){

        int i=Q.front().x,j=Q.front().y;
        inQueue[i][j]=0;
        Q.pop_front();
        timp--;
        Q.push_back({i,j});

        for(int d=0;d<4;++d){
            int ii=i+di[d],jj=j+dj[d];
            if(!isGood(ii,jj) || key.find(mt[ii][jj]) == key.end())
                continue;
            if(viz[ii][jj] && !inQueue[ii][jj])
                Q.push_back({ii,jj}),inQueue[ii][jj]=1;
            else if(!viz[ii][jj]){
                Q.push_front({ii,jj});
                key.insert((ii-1)*m+jj);
                timp=Q.size();
                viz[ii][jj]=1;
                inQueue[ii][jj]=1;
            }
        }

        if(!timp)
            break;
    }

    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
        if(viz[i][j]) ans++;
    fout<<ans;

    return 0;
}