Cod sursa(job #1592113)

Utilizator adiXMGemene Adrian adiXM Data 7 februarie 2016 00:45:04
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
const int NMAX=155;
int n,m,startx,starty;
int a[NMAX][NMAX],cheie[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];
inline void Read()
{
    int cam,cnt=0;
    f>>n>>m>>cam;
    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;
                viz[i][j]=1;
            }
        }
    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;
}
inline void Fill(int i,int j)
{
    viz[i][j]=1;
    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 Deblocheaza(int ind)
{
    for(int k=0;k<v[ind].size();k++)
        blocat[v[ind][k].first][v[ind][k].second]=0;
}
int main()
{
    Read();
    bool ok;
    vector < pair<int,int> > Q;
    do{
        ok=0;
        Q.clear();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(viz[i][j]==1)
                    Q.push_back(make_pair(i,j));
                if(blocat[i][j]==0 && cheie[i][j]==0)
                {
                    ok=1;
                    cheie[i][j]=1;
                    Deblocheaza(index[i][j]);
                }
            }
        for(int k=0;k<Q.size();k++)
            Fill(Q[k].first,Q[k].second);
    }
    while(ok);
    int sol=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sol+=viz[i][j];
    g<<sol<<"\n";
    return 0;
}