Cod sursa(job #54185)

Utilizator astronomyAirinei Adrian astronomy Data 24 aprilie 2007 15:05:14
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

#define MAXN 156
#define pb push_back

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

int N, M, K, xs, ys, B[MAXN][MAXN], A[MAXN][MAXN], Q[MAXN*MAXN];
char viz[MAXN][MAXN], uz[MAXN*MAXN];

vector<int> Key[MAXN*MAXN];

int valid(int x, int y)
{
    if(x < 1 || y < 1 || x > N || y > M || viz[x][y]) return 0;
    return 1;
}

void solve(void)
{
    int k, inc, sf, nx, ny, x, y, p;

    Q[inc = sf = 0] = (xs<<8)+ys, viz[xs][ys] = 1, uz[K] = 1;

    while(inc <= sf)
    {
        x = Q[inc]>>8, y = Q[inc++]&255;
        for(k = 0; k < 4; k++)
         if( valid(nx = x+dx[k], ny = y+dy[k]) )
         {
            if(uz[B[nx][ny]])
                Q[++sf] = (nx<<8)+ny, viz[nx][ny] = 1, uz[A[nx][ny]] = 1;
            else
                Key[B[nx][ny]].pb( (nx<<8)+ny );
         }
        for(k = (int)(Key[p = A[x][y]].size())-1; k >= 0; k--)
        {
            nx = Key[p][k]>>8, ny = Key[p][k]&255;
            if(!viz[nx][ny])
                viz[nx][ny] = 1, Q[++sf] = Key[p][k];
        }
    }
}

void read_data(void)
{
    int i, j, k;

    scanf("%d %d %d\n", &N, &M, &K);

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

    for(i = 1; i <= N; i++)
     for(j = 1; j <= M; j++)
      if(A[i][j] == K)
        xs = i, ys = j;
}

void write_data(void)
{
    int i, j, k;

    for(k = 0, i = 1; i <= N; i++)
     for(j = 1; j <= M; j++)
        k += viz[i][j];

    printf("%d\n", k);
}

int main(void)
{
    freopen("castel.in", "rt", stdin);
    freopen("castel.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}