Cod sursa(job #266433)

Utilizator cristiprgPrigoana Cristian cristiprg Data 25 februarie 2009 15:49:31
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <cstdio>
#include <cstdlib>

#define DIM 152
#define INF 127
int n, m, k, a[DIM][DIM],kmax;
char b[DIM][DIM];
const int vi[] = {-1, 0, 1, 0},
          vj[] = {0, 1, -1, 0};

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++)
             fscanf(f, "%d", &a[i][j]), b[i][j] = INF;
    fclose(f);
}

void afisare (FILE *f)
{

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
             if (b[i][j] != INF)
                 fprintf(f, "%3d", b[i][j]);
             else
                 fprintf(f, "  X");
        fprintf(f, "\n");
    }    
}

bool OK (int i, int j, int chei[])
{
    if (i < 1  || i > m || j < 1 || j > n)
        return false;
    
    if (b[i][j] != INF)
        return false;
        
    int pp = 0;
    for (int q = 1; q <= kmax; q++)
        if (chei[a[i][j]] == 1)
            {pp = 1;break;}
    
    if (pp == 0)
        return false;
    
    return true;
}


void lee (FILE *f)
{
    int dr, *coada, im, jm, i, j, room;
    //int *chei;
    int chei[9999];
    bool done = false;
    
    coada = new int [m*n];
   // chei = new int [m*n];
    

    dr = 1;
    i = k / n + 1;
    j = (k - 1) % n + 1;
    b[i][j] = 1;
    coada[1] = k;
    chei[k] = 1;
    kmax = k;
    while (!done)
    {
        done = true;

        for (int st = 1; st <= dr; st++)
        {
            i = coada[st] / n + 1;
            j = (coada[st] - 1) % n + 1;
            for (int d = 0; d < 4; d++)
            {
                 im = i + vi[d];
                 jm = j + vj[d]; 
                 room = (im - 1) * n + jm;
                 
                 
                 
                 if (OK (im, jm, chei))
                 {
                     done = false;
                     dr++;
                     coada[dr] = room;
                     b[im][jm] = 1;
                     chei[room] = 1;
                     if (room > kmax)
                        kmax = room;
                     
                 }
            }
         }

    }
    
    fprintf(f, "%d\n", dr);

}

int main ()
{
    citire ();

    FILE *f = fopen("castel.out", "w");
    lee (f);    
    //afisare(f);
    
    
    return 0;
}