Cod sursa(job #2162047)

Utilizator andonis1616And Cuz andonis1616 Data 11 martie 2018 23:37:18
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 150
using namespace std;
ifstream in ("castel.in");
ofstream out ("castel.out");

bool vizitat[NMAX+5][NMAX+5];
bool InCoada[NMAX+5][NMAX+5];
int n,m,k;
pair <int,int> ma[NMAX+5][NMAX+5];
int xinc,yinc,total;
vector < pair <int,int> > cine[NMAX+5][NMAX+5];

queue < pair <int,int> > q;

int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

void put(int *r,int *c,int key)
{
    if(key%m==0)
    {
        *r=key/m;
        *c=m;
    }
    else
    {
        *r=key/m+1;
        *c=key%m;
    }
}

bool valid(int r,int c)
{
    if(1<=r && 1<=c && r<=n && c<=m)
        return 1;
    return 0;
}

void incerc()
{
    int i,cam,r,c,rn,cn;
    put(&xinc,&yinc,k);
    q.push({xinc,yinc});
    vizitat[xinc][yinc]=true;
    while(!q.empty())
    {
        r=q.front().first;
        c=q.front().second;
        q.pop();
        for(i=0;i<4;i++)
        {
            rn=r+dx[i];
            cn=c+dy[i];
            for(int j=0;j<cine[r][c].size();j++)
            {
                int rxx=cine[r][c][j].first;
                int cxx=cine[r][c][j].second;
                if(InCoada[rxx][cxx]==1)
                {
                    q.push({rxx,cxx});
                    InCoada[rxx][cxx]=0;
                    vizitat[rxx][cxx]=1;
                }
            }
            cine[r][c].clear();
            if(valid(rn,cn) and vizitat[rn][cn]==0 and InCoada[rn][cn]==0)
            {
                int r_n=ma[rn][cn].first;
                int c_n=ma[rn][cn].second;
                if(vizitat[r_n][c_n])
                {
                    q.push({rn,cn});
                    for(int j=0;j<cine[rn][cn].size();j++)
                    {
                        int rxx=cine[rn][cn][j].first;
                        int cxx=cine[rn][cn][j].second;
                        if(InCoada[rxx][cxx]==1)
                        {
                            q.push({rxx,cxx});
                            InCoada[rxx][cxx]=0;
                            vizitat[rxx][cxx]=1;
                        }
                    }
                    cine[rn][cn].clear();
                    vizitat[rn][cn]=1;
                }
                else
                {
                    InCoada[rn][cn]=1;
                    cine[r_n][c_n].push_back({rn,cn});
                }
            }
        }
    }
}

int main()
{
    int i,j,x;
    in>>n>>m>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            {
                in>>x;
                put(&ma[i][j].first,&ma[i][j].second,x);
            }
    incerc();
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans+=vizitat[i][j];
    out<<ans;
    return 0;
}