Cod sursa(job #1804913)

Utilizator raulmuresanRaul Muresan raulmuresan Data 13 noiembrie 2016 11:29:07
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include<fstream>
#include<vector>
#include<string>
#include<queue>
#define modulo 666013

using namespace std;

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


string sir;
int i, n, m, k, j,x,y,t,lin,col,poz1,poz2,sol;
int a[159][159], viz[159][159],vizCheie[25000],b[159][159];
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};

vector<pair<int, int> > cheie[25000];

queue <pair<int, int> > q;

void init()
{
    int i,j;
    for(i=0;i<=n+1;i++)
    {
        for(j=0;j<=m+1;j++)
        {
            viz[i][j]=-1;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            viz[i][j]=0;
        }
    }
}


int main()
{
    fin >> n >> m >> k;
    init();
    x = 1;
    for(i = 1; i <= n; i++)
    {
       for(j = 1; j <= m; j++)
       {
           fin >> a[i][j];
           cheie[a[i][j]].push_back(make_pair(i,j));
           if(x == k)
           {
               q.push(make_pair(i,j));
               viz[i][j] = 1;
               vizCheie[x] = 1;
           }
           b[i][j] = x;
           x++;
       }
    }


    //fout<<q.front().first<<" "<<q.front().second<<"\n";
    while(! q.empty())
    {
        lin = q.front().first;
        col = q.front().second;
        //fout << lin <<" "<<col<<"\n";
        q.pop();
        x = b[lin][col];
        vizCheie[x] = 1;
        for(i = 0; i < cheie[x].size();i++)
        {
            poz1 = cheie[x][i].first;
            poz2 = cheie[x][i].second;
           // fout<<poz1<<" "<<poz2<<"\n";
            if(viz[poz1][poz2] == 0)
            {
                for(j=0;j<=3;j++)
                {
                    if(viz[poz1+dx[j]][poz2+dy[j]] == 1)
                    {
                        //fout << poz1 <<" " <<poz2<<"\n";
                        viz[poz1][poz2] = 1;
                        q.push(make_pair(poz1,poz2));
                        break;
                    }
                }
            }
        }
        for(j=0;j<=3;j++)
        {
            if(viz[lin+dx[j]][col+dy[j]] == 0 && vizCheie[a[lin+dx[j]][col+dy[j]]] == 1)
            {
                viz[lin+dx[j]][col+dy[j]] = 1;
                vizCheie[b[lin+dx[j]][col+dy[j]]] = 1;
                q.push(make_pair(lin+dx[j],col+dy[j]));
            }
        }

        //fout<<x<<"\n";
    }
    sol = 0;
    for(i = 1; i <= n; i++)
    {
       for(j = 1; j <= m; j++)
       {
            sol = sol + viz[i][j];
       }
    }
    fout << sol <<"\n";

     for(i = 1; i <= n; i++)
    {
       for(j = 1; j <= m; j++)
       {
            ////fout << viz[i][j] << " ";
       }
       //fout<<"\n";
    }
}