Cod sursa(job #2516440)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 31 decembrie 2019 15:03:32
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <vector>
#define K 155
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
int n,m,i,j,k,t,d,iv,jv,sol,p,u,val;
int a[K][K],f[K][K],cheie[K][K];
int di[]={0,1,0,-1};
int dj[]={1,0,-1,0};
vector <pair<int,int> > v[K*K]; ///v[i]=lista camere accesibile dupa ce luam cheia i
pair <int,int> c[K*K];
int lin(int x){
    if(x%m==0)return x/m;
    return x/m+1;
}
int col(int x){
    if(x%m==0)return m;
    return x%m;
}
int main(){
    fin>>n>>m>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j]; ///cheia necesara intrarii in camera (i,j)
    c[1]={lin(k),col(k)}; ///pun in coada toate camerele la care am acces
    f[lin(k)][col(k)]=1;  ///vizitata
    for(p=u=1;p<=u;p++){
        i=c[p].first;
        j=c[p].second;
        val=(i-1)*m+j;
        cheie[i][j]=1; ///iau cheia (val) doar cand intru in camera i,j
        for(t=0;t<v[val].size();t++)
            c[++u]=v[val][t];
        for(d=0;d<4;d++){
            iv=i+di[d];
            jv=j+dj[d];
            if(iv && jv && iv<=n && jv<=m && !f[iv][jv]){ ///nu am mai fost in camera iv,jv deja
                if(cheie[lin(a[iv][jv])][col(a[iv][jv])])
                    c[++u]={iv,jv};
                else v[a[iv][jv]].push_back({iv,jv});
                f[iv][jv]=1;
            }
        }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(cheie[i][j])
                sol++;
    fout<<sol;
    return 0;
}