Cod sursa(job #2596395)

Utilizator JafarakKarina Jafara Jafarak Data 9 aprilie 2020 18:04:54
Problema Castel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

const int N=155;

int a[N][N],n,m;
bool cheie[N*N],b[N][N];

const int di[6]={-1,0,1,0};
const int dj[6]={0,1,0,-1};

queue < pair < int, int > > que,v[N*N];

void Read ()
{
    int i,j,x;
    f>>n>>m;
    f>>x;
    i=(x-1)/m+1;
    j=x%m;
    cheie[x]=true;
    b[i][j]=true;
    que.push(make_pair(i,j));
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            f>>a[i][j];
}

void out ()
{
    int i,j;
    for(i=1;i<=n;i++,cout<<'\n')
        for(j=1;j<=m;j++)
            cout<<a[i][j]<<" ";
    cout<<que.front().first<<" "<<que.front().second<<'\n';
    for(i=1;i<=n;i++,cout<<'\n')
        for(j=1;j<=m;j++)
            cout<<b[i][j]<<" ";
    cout<<'\n';
}

bool oke ( int x, int y )
{
    if(x>n || y>m || x<1 || y<1)
        return false;
    if(b[x][y])
        return false;
    return true;
}

void add_new_rooms ( int x )
{
    while(!v[x].empty())
    {
        que.push(make_pair(v[x].front().first,v[x].front().second));
        cheie[(v[x].front().first-1)*m+v[x].front().second]=true;
        v[x].pop();
    }
}

int lee ()
{
    int t,i,j,inew,jnew,ct=0;
    while(!que.empty())
    {
        i=que.front().first;
        j=que.front().second;
        que.pop();
        ct++;
        for(t=0;t<4;t++)
        {
            inew=i+di[t];
            jnew=j+dj[t];
            if(oke(inew,jnew))
            {
                if(cheie[a[inew][jnew]])
                {
                    que.push(make_pair(inew,jnew));
                    b[inew][jnew]=true;
                    cheie[(inew-1)*m+jnew]=true;
                    add_new_rooms((inew-1)*m+jnew);
                }
                else
                {
                    v[a[inew][jnew]].push(make_pair(inew,jnew));
                    b[inew][jnew]=true;
                }

            }
        }
    }
    return ct;
}

int main()
{
    Read();
    g<<lee()<<'\n';
    //out();
    return 0;
}