Cod sursa(job #1047331)

Utilizator cypy2474alupei ciprian cypy2474 Data 4 decembrie 2013 11:30:32
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<fstream>
#define Q 30000
using namespace std;
int dx[]={0,0,-1,0,1};
int dy[]={0,-1,0,1,0};
int m[150][150],i,j,n,k,u,p,nr,xc,yc,key[Q],qx[Q],qy[Q],x[Q],y[Q],sol,sol1,M;
bool mat[150][150],check[150][150];
int main ()
{
    ifstream f("castel.in");
    ofstream g("castel.out");
    f>>n>>M>>k;
    qx[1]=k/M+1;
    qy[1]=k%M;
    for(i=1;i<=n;++i)
        for(j=1;j<=M;++j)
            f>>m[i][j];
    mat[qy[1]][qx[1]]=1;
    nr=sol=key[k]=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]]&&!mat[xc][yc])
                    {
                        ++sol;
                        mat[xc][yc]=1;
                        key[(xc-1)*M+yc]=1;
                        x[++u]=xc;
                        y[u]=yc;
                    }
                    else
                        if(!check[x[p]][y[p]])
                        {
                        check[x[p]][y[p]]=1;
                        qx[++nr]=x[p];
                        qy[nr]=y[p];
                        }
                }
                p++;
            }
        }
    }
    g<<sol;
    return 0;
}