Cod sursa(job #54229)

Utilizator filipbFilip Cristian Buruiana filipb Data 24 aprilie 2007 16:21:31
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#include <vector>
#define cod(x, y) (x * N + y)
#define NMax 155

using namespace std;

int N, M, K, C[NMax][NMax];
int q[NMax * NMax], pus[NMax * NMax], uz[NMax * NMax];

    int dx[4] = {+1, -1, 0, 0};
    int dy[4] = {0, 0, +1, -1};

vector<int> L[NMax * NMax];

int main(void)
{
    int i, j, k, ql = 0, qr = 0, x, y, sx, sy;
    vector<int>::iterator it;
    
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);

    scanf("%d %d %d", &M, &N, &K);
    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
        {
            scanf("%d", &C[i][j]);
            C[i][j]--;
        }
        
    K--;

    for (q[ql=qr=0]=K, pus[K] = 1; qr <= ql; qr++)
    {
        x = q[qr] / N; y = q[qr] % N;
        uz[cod(x, y)] = 1;

        for (k = 0; k < 4; k++)
        {
            sx = x + dx[k]; sy = y + dy[k];
            if (sx >= 0 && sy >= 0 && sx < M && sy < N && !pus[cod(sx, sy)])
            {
                if (uz[C[sx][sy]])
                { q[++ql] = cod(sx, sy); pus[q[ql]] = 1; }
                else
                    L[C[sx][sy]].push_back(cod(sx, sy));
            }
        }

        for (it = L[cod(x,y)].begin(); it != L[cod(x,y)].end(); it++)
            if (!pus[*it])
                q[++ql] = *it, pus[*it] = 1;

        L[cod(x,y)].clear();
        
    }

    printf("%d\n", ql + 1);

    return 0;
    
}