Cod sursa(job #863582)

Utilizator Kira96Denis Mita Kira96 Data 23 ianuarie 2013 22:09:55
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<stdio.h>
#define N 151
#define Q 30000
using namespace std;
int dx[]={0,0,-1,0,1};
int dy[]={0,-1,0,1,0};
int m[N][N],i,j,xi,yi,n,k,u,p,nr,xc,yc,key[Q],qx[Q],qy[Q],x[Q],y[Q],sol,sol1,M;
bool mat[N][N],check[N][N];
int main ()
{
    freopen ("castel.in","r",stdin);
    freopen ("castel.out","w",stdout);
    scanf("%d%d%d",&n,&M,&k);
    key[k]=1;
    while(k>M)
    {
        xi++;
        k-=M;
    }
    ++xi;
    qx[1]=xi;
    yi=k;
    qy[1]=yi;
    for(i=1;i<=n;++i)
        for(j=1;j<=M;++j)
            scanf("%d",&m[i][j]);
    sol=1;
    mat[xi][yi]=1;
    nr=1;
    sol1=-1;
    while(sol!=sol1)
    {
        sol1=sol;
        for(k=1;k<=nr;++k)
        {
            x[1]=qx[k];
            y[1]=qy[k];
            p=u=1;
            while(p<=u)
            {
                for(i=1;i<=4;++i)
                {
                    xc=x[p]+dx[i];
                    yc=y[p]+dy[i];
					if(xc<1||yc<1||xc>n||yc>M)
						continue;
                    if(!key[m[xc][yc]]&&!check[x[p]][y[p]])
                    {
                        check[x[p]][y[p]]=1;
                        qx[++nr]=x[p];
                        qy[nr]=y[p];
                    }
                    else
                    if(key[m[xc][yc]]&&!mat[xc][yc])
                    {
                        ++sol;
                        mat[xc][yc]=1;
                        key[(xc-1)*M+yc]=1;
                        x[++u]=xc;
                        y[u]=yc;
                    }
                }
                ++p;
            }
        }
    }
    printf("%d",sol);
    return 0;
}