Cod sursa(job #2145273)

Utilizator zhm248Mustatea Radu zhm248 Data 27 februarie 2018 11:21:37
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
queue<int>q;
vector<int>g[22501];
int v[22501],n,m;
bool f[22501];
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};
int dex(int k)
{
    if(k%n)
        return (k/n)+1;
    return k/n;
}

int dey(int k)
{
    return k-((dex(k)-1)*n);
}

int con(int x,int y)
{
    return n*(x-1)+y;
}

int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    int k,i;
    scanf("%d%d%d",&m,&n,&k);
    for(i=1; i<=n*m; ++i)
    {
        scanf("%d",&v[i]);
    }
    q.push(k);
    f[k]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(i=0; i<g[x].size(); ++i)
        {
            if(!f[g[x][i]])
            {
                f[g[x][i]]=1;
                q.push(g[x][i]);
            }
        }
        int xx=dex(x);
        int yy=dey(x);
        for(i=0; i<=3; ++i)
        {
            int valx=xx+dx[i];
            int valy=yy+dy[i];
            if(valx&&valy&&valx<=m&&valy<=n&&!f[con(valx,valy)])
            {
                if(f[v[con(valx,valy)]])
                {
                    f[con(valx,valy)]=1;
                    q.push(con(valx,valy));
                }
                else
                    g[v[con(valx,valy)]].push_back(con(valx,valy));
            }
        }
    }
    int nr=0;
    for(i=1; i<=n*m; ++i)
    {
        if(f[i])
            nr++;
    }
    printf("%d\n",nr);
    return 0;
}