Cod sursa(job #3208567)

Utilizator Andrei1507enea andrei Andrei1507 Data 28 februarie 2024 20:24:46
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <bits/stdc++.h>
using namespace std;
queue<int> q,key[23005];
int mat[155][155],cheie[23005],viz[23005];
signed main()
{
    ifstream cin("castel.in");
    ofstream cout("castel.out");
    int n,m,k,c,x,rez=0;
    int p;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mat[i][j];
        }
    }
    q.push(k);
    cheie[k]=1;
    while(!q.empty())
    {
        rez++;
        p=q.front();
        /*cout<<p<<'\n';
        cout<<key[6].size()<<'\n';
        for(int i=1;i<=n*m;i++)
        {
            cout<<cheie[i]<<" ";
        }
        cout<<'\n';*/
        viz[p]=1;
        while(!key[p].empty())
        {
            x=key[p].front();
            cheie[x]=1;
            q.push(x);
            key[p].pop();
        }
        q.pop();
        if(p-m>0&&viz[p-m]==0)
        {
            c=p-m;
            if(cheie[mat[(c-1)/m+1][(c-1)%m+1]]!=0)
            {
                cheie[c]=1;
                while(!key[c].empty())
                {
                    x=key[c].front();
                    cheie[x]=1;
                    q.push(x);
                    key[c].pop();
                }
                q.push(c);
            }
            else
            {
                //cout<<"***";
                key[mat[(c-1)/m+1][(c-1)%m+1]].push(c);
            }
            viz[p-m]=1;
        }
        if(p+m<=n*m&&viz[p+m]==0)
        {
            c=p+m;
            viz[p+m]=1;
            if(cheie[mat[(c-1)/m+1][(c-1)%m+1]]!=0)
            {
                cheie[c]=1;
                while(!key[c].empty())
                {
                    x=key[c].front();
                    cheie[x]=1;
                    q.push(x);
                    key[c].pop();
                }
                q.push(c);
            }
            else
            {
                //cout<<"***";
                key[mat[(c-1)/m+1][(c-1)%m+1]].push(c);
            }
        }
        if((p-1)%m!=0&&viz[p-1]==0)
        {
            c=p-1;
            viz[p-1]=1;
            if(cheie[mat[(c-1)/m+1][(c-1)%m+1]]!=0)
            {
                cheie[c]=1;
                while(!key[c].empty())
                {
                    x=key[c].front();
                    cheie[x]=1;
                    q.push(x);
                    key[c].pop();
                }
                q.push(c);
            }
            else
            {
                //cout<<"***";
                key[mat[(c-1)/m+1][(c-1)%m+1]].push(c);
            }
        }
        if(p%m!=0&&viz[p+1]==0)
        {
            c=p+1;
            viz[p+1]=1;
            if(cheie[mat[(c-1)/m+1][(c-1)%m+1]]!=0)
            {
                cheie[c]=1;
                while(!key[c].empty())
                {
                    x=key[c].front();
                    cheie[x]=1;
                    q.push(x);
                    key[c].pop();
                }
                q.push(c);
            }
            else
            {
                //cout<<"***";
                key[mat[(c-1)/m+1][(c-1)%m+1]].push(c);
                //cout<<mat[(c-1)/m+1][(c-1)%m+1]<<'\n';
            }
        }
    }
    //cout<<key[6].size()<<'\n';
    cout<<rez;
    return 0;
}
/**
i=x/m
j=x%m
*/