Cod sursa(job #63004)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 25 mai 2007 14:20:45
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <vector>
#define NMAX 160
#define QMAX ((1<<16)-1)

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

using namespace std;

vector<int> Key[NMAX];

int main()
{
        int cheie, i, j, lo, hi, l, c, ll, cc;

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

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

        Q[0] = K;
        Cheie[K] = 1;
        Desc[ K/N ][ K%M ] = 1;
        for (lo = 0, hi = 1; lo <= hi; lo = (lo+1)&QMAX)
        {
                l = Q[lo]/N; c = Q[lo]%M;
                Cheie[ A[l][c] ] = 1;

                for (i = Key[ A[l][c] ].size()-1; i >= 0; i--)
                    if (!Desc[ Key[ A[l][c] ][i]/N ][ Key[ A[l][c] ][i]%M ])
                    {
                        Desc[ Key[ A[l][c] ][i]/N ][ Key[ A[l][c] ][i]%M ] = 1;
                        Q[hi] = Key[ A[l][c] ][i]; hi = (hi+1)&QMAX;
                    }

                for (i = 0; i < 4; i++)
                   if (l+L[i] >= 0 && l+L[i] < N && c+C[i] >= 0 && c+C[i] < M)
                   {
                       if (Cheie[ A[ l+L[i] ][ c+C[i] ] ] && !Desc[ l+L[i] ][ c+C[i] ])
                          Q[hi] = (l+L[i])*N+c+C[i], hi = (hi+1)&QMAX;
                       else Key[ A[l+L[i]][c+C[i]] ].push_back((l+L[i])*N+c+C[i]);
                   }
        }

        for (i = 0; i < N; i++)
            for (j = 0; j < M; j++) NrCam+=Desc[i][j];

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

        return 0;

}