Cod sursa(job #2147486)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 28 februarie 2018 19:35:36
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int nmax=150;
int n,m,S;
bool viz[nmax+5][nmax+5];
bool InCoada[nmax+5][nmax+5];
int RI,CI;
struct data
{
    int r,c;
};
data v[nmax+5][nmax+5];
queue<data>q;
vector<data>cine[nmax+5][nmax+5];
int vf;
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;
}
int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1};
int main()
{
    fin>>n>>m>>S;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int a;
            fin>>a;
            put(&v[i][j].r,&v[i][j].c,a);
        }
    put(&RI,&CI,S);
    q.push({RI,CI});
    viz[RI][CI]=1;
    while(!q.empty())
    {
        int r=q.front().r;
        int c=q.front().c;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int rn=r+dr[i];
            int cn=c+dc[i];
            for(int j=0;j<cine[r][c].size();j++)
            {
                int rxx=cine[r][c][j].r;
                int cxx=cine[r][c][j].c;
                if(InCoada[rxx][cxx]==1)
                {
                    q.push({rxx,cxx});
                    InCoada[rxx][cxx]=0;
                    viz[rxx][cxx]=1;
                }
            }
            cine[r][c].clear();
            if(valid(rn,cn) && viz[rn][cn]==0 && InCoada[rn][cn]==0)
            {
                int r_n=v[rn][cn].r;
                int c_n=v[rn][cn].c;
                if(viz[r_n][c_n])
                {
                    q.push({rn,cn});
                    for(int j=0;j<cine[rn][cn].size();j++)
                    {

                        int rxx=cine[rn][cn][j].r;
                        int cxx=cine[rn][cn][j].c;
                        if(InCoada[rxx][cxx]==1)
                        {
                            q.push({rxx,cxx});
                            InCoada[rxx][cxx]=0;
                            viz[rxx][cxx]=1;
                        }
                    }
                    cine[rn][cn].clear();
                    viz[rn][cn]=1;
                }
                else
                {
                    InCoada[rn][cn]=1;
                    cine[r_n][c_n].push_back({rn,cn});
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans+=viz[i][j];
    fout<<ans;
	return 0;
}
/**

**/