Cod sursa(job #62996)

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

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

using namespace std;

vector<int> Cheie[NMAX], Curr;

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 < NMAX; i++)
            for (j = 0; j < NMAX; j++) A[i][j] = -1;

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

        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] > M) Trans[1][i] = 1, Trans[0][i]++;
        }

        NrCam = 1;
        Q[0][0] = Trans[0][K]; Q[1][0] = Trans[1][K];
        F[Q[0][0]][Q[1][0]] = 1;

        for (lo = 0, hi = 1; lo < hi; lo = (lo+1)&QMAX)
        {
                l = Q[0][lo]; c = Q[1][lo];
                cheie = Nr[l][c];

                for (i = 0; i < 4; i++)
                {
                        ll = l+L[i]; cc = c+C[i];
                        if (A[ll][cc]>=0 && !F[ll][cc])
                           Cheie[ A[ll][cc] ].push_back(Nr[ll][cc]);
                }

                for (j = Cheie[cheie].size()-1; j >= 0; j--)
                {
                    ll = Trans[0][ Cheie[cheie][j] ]; cc = Trans[1][ Cheie[cheie][j] ];
                    Q[0][hi] = ll; Q[1][hi] = cc; hi = (hi+1)&QMAX;
//                    printf("%d %d\n", ll, cc);
                    Desc[ll][cc] = 1;
                    for (i = 0; i < 4; i++)
                    {
                        ll += L[i]; cc += C[i];
                        if (A[ll][cc] >= 0 && !F[ll][cc])
                        {
                           F[ll][cc] = 1;
                           if (A[ll][cc] == cheie) Curr.push_back(Nr[ll][cc]);
                           else Cheie[ A[ll][cc] ].push_back(Nr[ll][cc]);
                        }
                    }
                }

                Cheie[ cheie ].clear();
                for (i = Curr.size()-1; i >= 0; i--) Cheie[cheie].push_back(Curr[i]);
                Curr.clear();
        }

        for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) NrCam+=Desc[i][j];
//        printf("-----\n");

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

        return 0;
        
}