Cod sursa(job #62123)

Utilizator infogodinfo god infogod Data 21 mai 2007 21:07:05
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#pragma option -3 -r -Z -O2 -ml

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>

#define MAX_N 155
#define FIN "castel.in"
#define FOUT "castel.out"

//#define far
//#define huge

//unsigned far A[MAX_N][MAX_N], far Q[MAX_N*MAX_N];

unsigned * huge key_list[MAX_N*MAX_N];
unsigned *A[MAX_N], *Q;

char  U[MAX_N][(MAX_N+7)/8], key[MAX_N][(MAX_N+7)/8];
//char far U[MAX_N][MAX_N];


unsigned Res, N, M, K, key_list[1000000];

const int di[] = {-1,+1, 0, 0};
const int dj[] = { 0, 0,-1,+1};

void set_u(int x, int y)
{
    U[x][y/8] |= (1<< (y%8));
}

int get_u(int x, int y)
{
    return ((U[x][y/8]) >> (y%8)) & 1;
}

void set_key(int x, int y)
{
    key[x][y/8] |= (1<<(y%8));
}

int get_key(int x, int y)
{
    return ((key[x][y/8]) >> (y%8))&1;
}

int main(void)
{
    int i, j, d, ii, jj;
    unsigned ql, qr, n;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%u %u %u", &N, &M, &K);
    for (i = 0; i < N; i ++) A[i] = (unsigned*) calloc(N, sizeof(unsigned));
    Q = (unsigned*)calloc(M*N, sizeof(unsigned));

    for (i = 0; i < N; i++)
        for (j = 0; j < M; j++)
        {
            scanf("%u", A[i]+j);
            ++Q[--A[i][j]];
        }

    for (i = 0; i < M*N; i++)
    {
        key_list[i] = (unsigned  far*)calloc(Q[i]+1, sizeof(unsigned));
        key_list[i] += Q[i];
        *key_list[i] = 65535;
    }

    Q[ql = qr = 0] = --K;

    memset(U, 0, sizeof(U));
    set_u(K/M, K%M);
//    U[K/M][K%M] = 1;
    for (; ql <= qr; ql++)
    {
        // am cheia N
        n = Q[ql];
        set_u(n/M, n%M); Res++;
        for (unsigned *it = key_list[n]; *it != 65535; it++)
            if (!get_u(*it/M,*it%M))
            {
                Q[++qr] = *it;
                set_u(*it/M,*it%M);
            }
        i = n/M; j = n%M;
        for (d = 0; d < 4; d++)
        {
            ii = i+di[d], jj = j+dj[d];
            if (ii < 0 || jj < 0 || ii >= N || jj >= M || get_u(ii,jj)) continue;
            if (get_u(A[ii][jj]/M, A[ii][jj]%M))
            {
                Q[++qr] = ii*M+jj;
                set_u(ii, jj);
            }
            else
            if (!get_key(A[ii][jj]/M, A[ii][jj]%M))
            {

                *(-- key_list[ A[ii][jj] ]) = ii*M+jj;

                set_key(A[ii][jj]/M, A[ii][jj]%M);

//                 key_list[A[ii][jj]].push_back(ii*M+jj);
            }
        }
    }

    printf("%u\n", Res);

    return 0;
}