Cod sursa(job #3123013)

Utilizator Raul_AArdelean Raul Raul_A Data 21 aprilie 2023 17:49:22
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>
using namespace std;

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

#define cin in
#define cout out

int n,m,k;
int a[155][155];

bitset<155> drum[155];
vector< pair<int,int> > P;
queue< pair<int,int> > Q;
bitset<24000> key;

const int di[]={-1,1,0,0};
const int dj[]={0,0,-1,1};

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

void lee() 
{
    while(!Q.empty())
    {
        pair<int,int> x=Q.front();
        
        Q.pop();
        
        for(int d=0;d<4;d++)
        {
            int ii=di[d]+x.first;
            int jj=dj[d]+x.second;
            
            if(inside(ii,jj) && key[a[ii][jj]] && drum[ii][jj]==0)
            {
                drum[ii][jj]=1;
                int nr=(ii-1)*m+jj;
            
                key[nr]=1;
                
                Q.push({ii,jj});
                P.push_back({ii,jj});
            }
        }
    }
}

int main()
{
    cin>>n>>m>>k;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
       
    k--;
    int i=k/m+1,j=k%m+1;
    
    Q.push({i,j});
    P.push_back({i,j});
    
    key[k++]=1;
    key[a[i][j]]=1;
    
    drum[i][j]=1;
    
    bool ok=1;
    while(ok)
    {
        lee();
        for(auto x: P)
        {
            for(int d=0;d<4;d++)
            {
                int ii=di[d]+x.first;
                int jj=dj[d]+x.second;
            
                if(inside(ii,jj) && drum[ii][jj]==0 && key[a[ii][jj]])
                {
                    drum[ii][jj]=1;
                    int nr=(ii-1)*m+jj;
            
                    key[nr]=1;
                
                    Q.push({ii,jj});
                    P.push_back({ii,jj});
                }
            }
        }
        
        if(Q.empty())
            ok=0;
    }
    
    cout<<P.size();

    return 0;
}