Cod sursa(job #931007)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 27 martie 2013 22:26:05
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");

struct coada
{
    int x;
    int y;
};

coada q[25000];

int dx[] = {-1, +1, 0, 0};
int dy[] = {0, 0, -1, 1};

int n,m,k,i,j,a[155][155],ql,qr,x,y,nrc;
bool viz[23000],key[23000],ok;

int camera(int i, int j)
{
    return (i-1)*m+j;
}

void solve()
{
    if (k%m==0)
    {
        q[1].x=k/m;
        q[1].y=m;
    }
    else
    {
        q[1].x=k/m+1;
        q[1].y=k%m;
    }
    ql=1;
    qr=1;
    viz[k]=true;
    key[k]=true;
    ok=true;
    while (ok==true)
    {
        ok=false;
        ql=1;
        for (i=ql;i<=qr;i++)
        {
            for (j=0;j<=3;j++)
            {
                x=q[i].x+dx[j];
                y=q[i].y+dy[j];
                if (x>=1 && y>=1 && x<=n && y<=m)
                {
                    qr++;
                    q[qr].x=x;
                    q[qr].y=y;

                    if (viz[camera(x,y)]==false && key[a[x][y]]==true)
                    {
                        key[camera(x,y)]=true;
                        viz[camera(x,y)]=true;
                        ok=true;
                        nrc++;
                    }
                }
            }
            ql++;
        }
    }
}

int main()
{
    f>>n>>m>>k;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            f>>a[i][j];
    solve();
    g<<nrc;
    f.close();
    g.close();
    return 0;
}