Cod sursa(job #2780683)

Utilizator puica2018Puica Andrei puica2018 Data 7 octombrie 2021 18:06:48
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,k;
int a[155][155],cheie[155*155],vis[155*155];
pair <int,int> a1[155*155];
vector <int> pos[155*155];
queue <int> q;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

int main()
{
    fin>>n>>m>>k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            fin>>a[i][j];
    int aux=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            a1[++aux]=make_pair(i,j);
    q.push(k);
    cheie[k]=1;
    vis[k]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        cheie[x]=1;
        for(auto p:pos[x])
        {
            if(!vis[p])
            {
                q.push(p);
                vis[p]=1;
            }
        }
        int i=a1[x].first,j=a1[x].second;
        for(int d=0; d<4; d++)
        {
            int iv=i+dx[d],jv=j+dy[d];
            if(iv<1 && iv>n && jv<1 && jv>m)
                continue;
            if(vis[(iv-1)*m+jv]==1)
                continue;
            if(cheie[a[iv][jv]])
            {
                q.push((iv-1)*m+jv);
                vis[(iv-1)*m+jv]=1;
            }
            else
                pos[a[iv][jv]].push_back((iv-1)*m+jv);
        }
    }
    int ans=0;
    for(int i=1; i<=n*m; i++)
        ans+=vis[i];
    fout<<ans<<"\n";
    return 0;
}