Cod sursa(job #2563392)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 1 martie 2020 11:13:39
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
int n,m,v[201][201],k,ans;
vector<int> nums,toreach[22701];
set<int> sol[151][151];
queue< pair<int,int> > coada;
bitset<10000001> reuniune;
bool use[201][201];
int dirx[5]={-1,1,0,0};
int diry[5]={0,0,-1,1};
int main()
{
    fin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            fin>>v[i][j];
            sol[i][j].insert(m*(i-1)+j);
        }
    int x=k/m+1;
    int y=k%m;
    if(y==0)
    {
        y=m;
        x--;
    }
    coada.push({x,y});
    use[x][y]=1;
    while(!coada.empty())
    {
        x=coada.front().first;
        y=coada.front().second;
        int cheie=0;
        if(reuniune[(x-1)*m+y]==0)
        {
            reuniune[(x-1)*m+y]=1;
            cheie=(x-1)*m+y;
        }
        use[x][y]=1;
        for(int i=0;i<4;i++)
        {
            x+=dirx[i];
            y+=diry[i];
            if(x>0&&x<=n&&y>0&&y<=m&&use[x][y]==0)
            {
                if(reuniune[v[x][y]]==1)
                    coada.push({x,y});
                else
                toreach[v[x][y]].push_back((x-1)*m+y);
            }
            x-=dirx[i];
            y-=diry[i];
        }
        if(cheie)
        {
            nums.clear();
            for(auto it=toreach[cheie].begin();it!=toreach[cheie].end();it++)
            {
                int nr=*it;
                x=nr/m+1;
                y=nr%m;
                if(y==0)
                {
                    y=m;
                    x--;
                }
                if(reuniune[v[x][y]]&&use[x][y]==0)
                {
                    coada.push({x,y});
                    nums.push_back(nr);
                    use[x][y]=1;
                }
            }
            toreach[cheie].clear();
        }
        coada.pop();
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           ans+=use[i][j];
    fout<<ans;
    /*for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(use[i][j])
    {
        set<int> sss=sol[i][j];
        for(auto it=sss.begin();it!=sss.end();it++)
            fout<<*it<<" ";
        fout<<'\n';
    }*/
    return 0;
}