Cod sursa(job #2702054)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 2 februarie 2021 18:26:55
Problema Castel Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <bits/stdc++.h>
#define vt vector
#define INF 1e9
#define pb push_back

using namespace std;

int n,m,k;
vector<vector<int> >v(153,vt<int>(153));
vector<pair<int,int>> id(22503);
vector<vector<int> >id2(153,vector<int>(153));
vector<vector<int> >d(22503);
vector<bool>viz(22503);

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

bool ok(int x,int y){
    return x>=1 && x<=n && y>=1 && y<=m;
}

void bfs(){
    queue<int>q;
    q.push(k);
    viz[k]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();

        for(int i=0;i<d[x].size();i++){
            if(!viz[d[x][i]]){
                viz[d[x][i]]=1;
                q.push(d[x][i]);
            }

        }

        for(int i=0;i<4;i++){
            int newx=id[x].first+dx[i];
            int newy=id[x].second+dy[i];

            if(ok(newx,newy)){
                if(viz[v[newx][newy]] && !viz[id2[newx][newy]]){
                    viz[id2[newx][newy]]=1;
                    q.push(id2[newx][newy]);
                }
            }

        }

    }


}

int dfs2(){
    queue<int>q;
    q.push(k);

    int sol=0;
    while(!q.empty()){
        int x=id[q.front()].first;
        int y=id[q.front()].second;
        q.pop();

        for(int i=0;i<4;i++){
            int newx=x+dx[i];
            int newy=y+dy[i];

            if(ok(newx,newy) && viz[id2[newx][newy]]){
                q.push(id2[newx][newy]);
                viz[id2[newx][newy]]=0;
                sol++;
            }

        }
    }

    return sol;

}

int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);

    scanf("%d %d %d",&n,&m,&k);

    int nr=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&v[i][j]);
            nr++;
            d[v[i][j]].push_back(nr);
            id[nr].first=i;
            id[nr].second=j;
            id2[i][j]=nr;
        }
    }

    bfs();


    printf("%d",dfs2());


    return 0;
}