Cod sursa(job #2433584)

Utilizator MaraPMara P MaraP Data 28 iunie 2019 00:49:36
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include<fstream>
#include <queue>
using namespace std;
queue <pair <int, int > > Q;
const int di[]={-1,0,1,0};
const int dj[]={0,-1,0,1};
int a[155][155], ap[22505], b[155][155],n,m,k;
void citire()
{
    ifstream fin("castel.in");
    fin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fin>>a[i][j];
}
void bordare()
{
    for(int i=0;i<=n+1;i++)
    {
        b[i][0]=-1;
        b[i][n+1]=-1;
    }
    for(int i=0;i<=m+1;i++)
    {
        b[0][i]=-1;
        b[m+1][i]=-1;
    }
}
void lee(pair <int, int> start)
{
    bordare();
    int ok=1;
    b[start.first][start.second]=1;
    ap[k]=1;
    int ant=0,c=0;
    while(ok==1)
    {
        ok=0; Q.push(start);
        c=0;
        while(!Q.empty())
        {
            pair <int, int> nod=Q.front();
            Q.pop();
            for(int k=0;k<4;k++)
            {
                int vi=nod.first+di[k];
                int vj=nod.second+dj[k];
                if(b[vi][vj]==0&&ap[a[vi][vj]]!=0)
                {
                    ok=1;
                    b[vi][vj]=1;
                    ap[(vi-1)*m+vj]=1;
                    Q.push(make_pair(vi,vj));
                    c++;
                }
            }
        }
        if(ok==1)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    b[i][j]=0;
        if(c==ant)
            break;
        else
            ant=c;
    }

}
void afisare()
{
    ofstream fout("castel.out");
    int nr=0;
    for(int i=1;i<=m*n;i++)
        if(ap[i]!=0)
            nr++;
    fout<<nr;
}
int main()
{
    citire();
    int i,j;
    j=k%m;
    if(j==0)
        j=m;
    i=k/m+1;
    if(k%m==0)
        i--;
    pair <int, int > start=make_pair(i,j);
    lee(start);
    afisare();
    return 0;
}