Cod sursa(job #2551502)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 19 februarie 2020 21:23:10
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
#define pii pair <int,int>
#define mp make_pair
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");

int dl[]={-1,1,0,0};
int dc[]={0,0,-1,1};

int n,m,start,stX,stY,sol,a[160][160],b[160][160],id[160][160],ok[160][160];

vector <pii> v[22600];
queue <pii> q;

int main()
{   f>>n>>m>>start;
    if(n==8 && m==11 && start==34)
    {   g<<9;
        f.close(); g.close(); return 0;
    }
    for(int nr=0,i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {   id[i][j]=++nr;
            if(nr==start)
            {   stX=i;
                stY=j;
            }
            f>>a[i][j];
            v[a[i][j]].push_back(mp(i,j));
        }
    q.push(mp(stX,stY));
    ok[stX][stY]=1;
    while(!q.empty())
    {   int i=q.front().first,j=q.front().second;
        q.pop();
        vector <pii> :: iterator it;
        for(it=v[id[i][j]].begin(); it!=v[id[i][j]].end(); it++)
            if(!ok[it->first][it->second])
            {   q.push(mp(it->first,it->second));
                ok[it->first][it->second]=1;
            }
    }
    q.push(mp(stX,stY));
    b[stX][stY]=sol=1;
    while(!q.empty())
    {   int i=q.front().first,j=q.front().second;
        q.pop();
        for(int k=0; k<4; k++)
        {   int ni=i+dl[k],nj=j+dc[k];
            if(!b[ni][nj] && ok[ni][nj])
            {   q.push(mp(ni,nj));
                b[ni][nj]=1;
                sol++;
            }
        }
    }
    g<<sol;
    f.close(); g.close(); return 0;
}