Cod sursa(job #62965)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 25 mai 2007 11:17:31
Problema Castel Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#define NMAX 160
#define QMAX ((1<<15)-1)

int Trans[2][NMAX], A[NMAX][NMAX], Nr[NMAX][NMAX], F[NMAX][NMAX];
int N, M, K, NrCam, Cheie[NMAX*NMAX], Q[2][QMAX];
int L[] = {0, 0, 1,-1};
int C[] = {1,-1, 0, 0};

int main()
{
        int nrmax, i, j, lo, hi, l, c;

        freopen("castel.in", "r", stdin);
        scanf("%d %d %d", &N, &M, &K);

        for (i = 0; i < NMAX; i++) for (j = 0; j < NMAX; j++) F[i][j] = 1;

        for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) scanf("%d", &A[i][j]), Nr[i][j] = ++NrCam, F[i][j] = 0;

        Trans[0][0] = 1;
        for (i = 1; i <= N*M; i++)
        {
            Trans[0][i] = Trans[0][i-1]; Trans[1][i] = Trans[1][i-1]+1;
            if (Trans[1][i] > N) Trans[1][i] = 1, Trans[0][i]++;
        }

        NrCam = 0;

        Q[0][0] = Trans[0][K]; Q[1][0] = Trans[1][K];
        for (lo = 0, hi = 1; lo <= hi; lo = (lo+1)&QMAX)
        {
                l = Q[0][lo]; c = Q[1][lo];
                Cheie[ Nr[l][c] ] = 1;
                for (i = 0; i < 4; i++)
                    if (Cheie[ A[l+L[i]][c+C[i]] ])
                    {
                       Q[0][hi] = l+L[i]; Q[1][hi] = c+C[i];
                       hi = (hi+1)&QMAX;
                       F[l+L[i]][c+C[i]] = 1;
                    }
        }

        for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) NrCam+=F[i][j];

        freopen("castel.out", "w", stdout);
        printf("%d\n", NrCam);

        return 0;
        
}