Cod sursa(job #3170729)

Utilizator The_SupremacySus Impostor The_Supremacy Data 18 noiembrie 2023 08:54:46
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 150;
int n,m;
short mat[NMAX+5][NMAX+5];
bitset<155>viz[155];
queue<short>q;
int dlin[6]={0,1,0,-1};
int dcol[6]={1,0,-1,0};
vector< short >G[NMAX*NMAX+5];
int cnt=0;bitset<NMAX*NMAX+5>cheie;
short linie,coloana;
void F(short val_cheie){
    if(G[val_cheie].size()==0){return;}
    for(int i=0;i<G[val_cheie].size();i++){
        cnt++;
        linie=G[val_cheie][i]/m;linie++;coloana=G[val_cheie][i]%m;
        if(coloana==0){coloana=m;linie--;}
        q.push((linie-1)*m+coloana);
        cheie[(linie-1)*m+coloana]=1;
        F((linie-1)*m+coloana);
    }
    G[val_cheie].clear();
}
int nr;
void BFS(int x,int y){
    viz[x][y]=1;cnt++;
    q.push((x-1)*m+y);
    cheie[(x-1)*m+y]=1;
    while(!q.empty()){
        nr=q.front();q.pop();
        int i=nr/m,j=nr%m;i++;if(j==0){j=m;i--;}
        for(int dir=0;dir<4;dir++){
            int i1=i+dlin[dir],j1=j+dcol[dir];
            if(i1>=1&&i1<=n&&j1>=1&&j1<=m&&viz[i1][j1]==0){
                viz[i1][j1]=1;
                if(cheie[mat[i1][j1]]==1){
                    cnt++;q.push((i1-1)*m+j1);
                    cheie[(i1-1)*m+j1]=1;
                    F((i1-1)*m+j1);
                }
                else{
                    G[mat[i1][j1]].push_back((i1-1)*m+j1);
                }
            }
        }
    }
}
int main()
{
    ifstream fin("castel.in");
    ofstream fout("castel.out");
    int k,l,c;
    fin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fin>>mat[i][j];
        }
    }
    l=k/m;c=k%m;l++;if(c==0){c=m;l--;}
    BFS(l,c);fout<<cnt<<'\n';
    return 0;
}