Cod sursa(job #2780609)

Utilizator puica2018Puica Andrei puica2018 Data 7 octombrie 2021 13:05:57
Problema Castel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

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

int m,n,k;
int a[155][155],cheie[155*155],vis[155*155];
pair <int,int> pos[155*155];

set <int> st;

int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

void neigh(int v)
{
    int i=pos[v].first,j=pos[v].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 && vis[(iv-1)*m+jv]==0)
            st.insert((iv-1)*m+jv);
    }
}

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 cnt=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            pos[++cnt]=make_pair(i,j);
    cheie[k]=1;
    vis[k]=1;
    neigh(k);
    bool can=1;
    while(can)
    {
        can=0;
        set <int> :: iterator it=st.begin();
        for(; it!=st.end(); it++)
        {
            int v=*it;
            int i=pos[v].first,j=pos[v].second;
            if(cheie[a[i][j]])
            {
                cheie[v]=1;
                vis[v]=1;
                set <int> :: iterator it1=it;
                it1++;
                st.erase(it,it1);
                neigh(v);
                can=1;
            }
        }
    }
    int ans=0;
    for(int i=1; i<=n*m; i++)
        ans+=vis[i];
    fout<<ans<<"\n";
    return 0;
}