Cod sursa(job #261393)

Utilizator cristiprgPrigoana Cristian cristiprg Data 18 februarie 2009 10:39:12
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <cstdio>
#define INF 99999
#define DIM 152
struct nod
{
    int coadai, coadaj;
    nod *next;
};

int i,j,n,m,k, a[DIM][DIM], b[DIM][DIM],  nr_chei, chei[DIM*DIM];
const int vi[]={-1, 0, 1, 0},
          vj[]={0, 1, 0, -1};

void citire ()
{
    FILE *f = fopen ("castel.in", "r");
    fscanf (f, "%d%d%d", &m, &n, &k);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = INF, fscanf(f, "%d", &b[i][j]);
    fclose(f);
}


bool OK(int i, int j)
{
    if (i < 1 || i > m || j < 1 || j > n) return 0;
    if (a[i][j] != INF)     return 0;
    //int q = n*(i-1)+j;//q = numarul camerei
    //printf ("i = %d; j = %d; camera:%d\n", i, j, q);
    int pp=0;
    for (int l = 1; l <= nr_chei; l++)
        if (chei[l] == b[i][j])
            {pp = 1; break;}

    if (pp == 0)    return 0;


    return 1;
}

void lee()
{
    i = k/m + 1;
    j = (k-1)%n + 1;
    nr_chei = 1;
    chei[1]=k;
    nod *p, *u, *t;
    p = new nod;
    u=p;
    p->next = NULL;

    p->coadai = i;
    p->coadaj = j;
    int ii, jj, prima_data=1,im,jm;
    a[i][j] = 1;

    while (p!=NULL)
    {
        ii = p->coadai;
        jj = p->coadaj;
        for (int d = 0; d < 4; d++)
        {
            im = ii + vi[d];
            jm = jj + vj[d];
            if (OK (im, jm))
            {
                nr_chei++;
                int q = n*(im-1)+jm;
                chei[nr_chei]=q;
                t = new nod;
                t->coadai = im;
                t->coadaj = jm;
                t->next = NULL;
                u->next = t;
                u = t;
                //a[t->coadai][t->coadaj] = a[ii][jj] + 1;
                a[t->coadai][t->coadaj] = 1;

            }
        }
        if (prima_data)
            prima_data = 0;

        else
        {
            t = p;
            p = p->next;
            delete t;
            prima_data = 1;
        }
    }
}

int main ()
{
    citire();
    lee();
    FILE *f = fopen ("castel.in", "w");
    //printf ("%d %d", m ,n);
    /*for (int q = 1; q <= m; q++)
    {
        for (int k = 1; k <= n; k++)
          if (a[q][k]==1)
            fprintf(f, "%3d", a[q][k]);
            else
            fprintf(f, "  X");

        fprintf (f, "\n");
        }*/
    int camere=0;
    for (int l = 1; l <= m; l++)
        for (int c = 1; c <= n; c++)
            if (a[l][c]== 1)
                camere++;
    fprintf (f, "%d", camere+1);
    return 0;
}