Cod sursa(job #3138381)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 19 iunie 2023 11:51:06
Problema Castel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <bits/stdc++.h>
#define NMAX 200
#define endl '\n'

using namespace std;

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

queue<pair<int,int>> Q;
vector<pair<int,int>> momentan;
bitset<NMAX> viz[NMAX];
int matlee[NMAX][NMAX],ans,n,m,k,a[NMAX][NMAX],poz[NMAX][NMAX],nr,fr[NMAX*NMAX+1];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool ok;
inline bool inmat(int i,int j)
{
    if(i >= 1 and i <= n and j >= 1 and j <= m)
        return true;
    return false;
}
inline bool verif(int i,int j)
{
    if(fr[a[i][j]] != 0)
        return true;
    return false;
}
inline void verif2()
{
    for(int i=0; i < momentan.size(); i++)
    {
        if(momentan[i].first != -1 and momentan[i].second != -1 and fr[a[momentan[i].first][momentan[i].second]] != 0)
        {
            Q.push({momentan[i].first,momentan[i].second});
            viz[momentan[i].first][momentan[i].second] = 1;
            momentan[i].first = -1;
            momentan[i].second = -1;
        }
    }
}
int main()
{
    nr = 1;
    fin >> n >> m >> k;
    for(int i=1; i <= n; i++)
        for(int j=1; j <= m; j++)
            fin >> a[i][j], poz[i][j] = nr++;
    for(int i=1; i <= n; i++)
    {
        for(int j=1; j <= m; j++)
        {
            if(poz[i][j] == k)
            {
                ok = 1;
                Q.push({i,j});
                fr[a[i][j]]++;
                viz[i][j] = 1;
                    while(!Q.empty())
                    {
                        for(int k=0; k < 4; k++)
                        {
                            int ii = Q.front().first + dx[k];
                            int jj = Q.front().second + dy[k];
                            if(inmat(ii,jj) and !viz[ii][jj] and verif(ii,jj))
                            {
                                Q.push({ii,jj});
                                viz[ii][jj] = 1;
                                fr[poz[ii][jj]]++;
                                verif2();
                            }
                            else if(inmat(ii,jj) and !viz[ii][jj] and !verif(ii,jj))
                            {
                                momentan.push_back({ii,jj});
                            }
                        }
                        Q.pop();
                    }
                    break;
                }
            }if(ok)
            break;
        }
    for(int i=1; i <= n; i++)
    {
        for(int j=1; j <= m; j++)
        {
            if(viz[i][j])
                ans++;
        }
    }
    fout << ans;
    return 0;
}