Cod sursa(job #1592136)

Utilizator adiXMGemene Adrian adiXM Data 7 februarie 2016 01:57:06
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
const int NMAX=155;
int n,m,sol,poz,startx,starty;
int a[NMAX][NMAX],blocat[NMAX][NMAX],index[NMAX][NMAX],viz[NMAX][NMAX];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
vector < pair<int,int> > v[NMAX*NMAX],Q[2];
inline void Fill(int i,int j)
{
    if(viz[i][j])
        return;
    viz[i][j]=1;
    sol++;
    Q[1].push_back(make_pair(i,j));
    for(int k=0;k<4;k++)
    {
        int x=i+dx[k];
        int y=j+dy[k];
        if(viz[x][y]==0 && blocat[x][y]==0)
            Fill(x,y);
    }
}
inline void Read()
{
    int cam,cnt=0;
    f>>n>>m>>cam;
    for(int i=0;i<=n+1;i++)
        blocat[i][m+1]=blocat[i][0]=1;
    for(int i=0;i<=m+1;i++)
        blocat[n+1][i]=blocat[0][i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f>>a[i][j];
            v[a[i][j]].push_back(make_pair(i,j));
            blocat[i][j]=1;
            cnt++;
            index[i][j]=cnt;
            if(cnt==cam)
            {
                startx=i;
                starty=j;
                blocat[i][j]=0;
            }
        }
}
inline void Deblocheaza(int ind)
{
    for(int k=0;k<v[ind].size();k++)
    {
        blocat[v[ind][k].first][v[ind][k].second]=0;
        for(int ii=0;ii<4;ii++)
        {
            int x=v[ind][k].first+dx[ii];
            int y=v[ind][k].second+dy[ii];
            if(viz[x][y]==1)
            {
                Q[0].push_back(v[ind][k]);
                break;
            }
        }
    }
}
int main()
{
    Read();
    Fill(startx,starty);
    do{
        Q[0].clear();
        for(int k=0;k<Q[1].size();k++)
            Deblocheaza(index[Q[1][k].first][Q[1][k].second]);
        Q[1].clear();
        for(int k=0;k<Q[0].size();k++)
            Fill(Q[0][k].first,Q[0][k].second);
    }
    while(Q[0].size());
    g<<sol<<"\n";
    return 0;
}