Cod sursa(job #2563408)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 1 martie 2020 11:21:26
Problema Castel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>
#define NMAX 155

using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
bitset<NMAX*NMAX> parcurse,chei;
vector<int> adiac[NMAX*NMAX];
int b[NMAX][NMAX],n,m,dc[4]={0,1,0,-1},dl[4]={1,0,-1,0};
int Hash(int Ox,int Oy){
    return (Ox-1)*n+Oy;
}
pair<int,int> unhash(int x)
{
    int Ox=x/n+1,Oy=x%n;
    if(Oy==0) Oy=n;
    return {Ox,Oy};
}
void lee(int p){
    queue<int> q;
    q.push(p);
    while(!q.empty()){
        chei[b[unhash(q.front()).first][unhash(q.front()).second]]=1;
        int Ox=unhash(q.front()).first,Oy=unhash(q.front()).second;
        for(int d=0;d<4;d++){
            int Ox1=Ox+dc[d],Oy1=Oy+dl[d];
            if(Ox1>=1 && Ox1<=n && Oy1>=1 && Oy1<=m && chei[b[Ox1][Oy1]] && parcurse[Hash(Ox1,Oy1)]==0){
                parcurse[Hash(Ox1,Oy1)]=1;
                q.push(Hash(Ox1,Oy1));
            }
        }
        for(int i=0;i<adiac[Hash(Ox,Oy)].size();i++){
            int Ox2=unhash(adiac[Hash(Ox,Oy)][i]).first,Oy2=unhash(adiac[Hash(Ox,Oy)][i]).first;
            if(parcurse[Hash(Ox2,Oy2)]==0)
            for(int d=0;d<4;d++){
                int Ox1=Ox2+dc[d],Oy1=Oy2+dl[d];
                if(Ox1>=1 && Ox1<=n && Oy1>=1 && Oy1<=m && parcurse[Hash(Ox1,Ox2)]){
                    chei[b[Ox2][Oy2]]=1;
                    parcurse[Hash(Ox2,Oy2)]=1;
                    break;
                    q.push(Hash(Ox2,Oy2));
                }
            }
        }
        q.pop();
    }
    fout<<parcurse.count();
}
int main()
{
    int p;
    fin>>n>>m>>p;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fin>>b[i][j];
            adiac[b[i][j]].push_back(Hash(i,j));
        }
    }
    parcurse[p]=1;
    lee(p);
    return 0;
}