Cod sursa(job #3138444)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 19 iunie 2023 16:45:52
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <fstream>
#include <queue>
#include <bitset>
#define NMAX 200

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];
short 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;
bool inmat(int i,int j)
{
    if(i < 1 or i > n or j < 1 or j > m)
        return false;
    return true;
}
bool verif(int i,int j)
{
    if(fr[a[i][j]] == 1)
        return true;
    return false;
}
void verif2()
{
    for(int i=0; i < momentan.size(); i++)
    {
        if(!viz[momentan[i].first][momentan[i].second] and fr[a[momentan[i].first][momentan[i].second]] == 1)
        {
            Q.push({momentan[i].first,momentan[i].second});
            viz[momentan[i].first][momentan[i].second] = 1;
            ans++;
            fr[poz[momentan[i].first][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});
                ans=1;
                fr[poz[i][j]] = 1;
                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;
                            ans++;
							fr[poz[ii][jj]] = 1;
                            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;
    }
    verif2();
    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;
                            ans++;
							fr[poz[ii][jj]] = 1;
                            verif2();
                        }
                        else if(inmat(ii,jj) and !viz[ii][jj] and !verif(ii,jj))
                        {
                            momentan.push_back({ii,jj});
                        }
                    }
                    Q.pop();
                }
    fout << ans;
    return 0;
}