Cod sursa(job #74094)

Utilizator andrei_infoMirestean Andrei andrei_info Data 23 iulie 2007 23:41:07
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#include <vector.h>

#define MAX 155

int a[MAX][MAX], viz[MAX][MAX], Q[MAX*MAX], rez,n,m,k, key[MAX*MAX];

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

vector<int> key_list[MAX*MAX];

void citire()
{
        freopen("castel.in", "r", stdin);
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0; i<n; i++)
                for (int j=0; j<m; j++)
                {
                        scanf("%d", &a[i][j]);
                        a[i][j]--;
                }
}

void calc()
{
        int ql,qr;
        ql=qr=0;
        Q[ql] = --k;
        viz[k/m][k%m] = 1;


        for ( ; ql<=qr; ql++)
        {
                int p = Q[ql]; rez++;
                key[p] = 1;
                for (vector<int>::iterator it = key_list[p].begin(); it != key_list[p].end(); ++it)
                        if (!viz[*it/m][*it%m])
                        {
                                Q[++qr] = *it;
                                viz[*it/m][*it%m]=1;
                        }
                int i = p/m, j = p%m;
                for (int k=0; k<4; k++)
                {
                        int ii = i+dx[k], jj= j+dy[k];
                        if (ii<0 || jj < 0 || ii >= n || jj >= m || viz[ii][jj] ) continue;
                        if ( key[a[ii][jj]])
                        {
                                Q[++qr] = ii*m+jj;
                                viz[ii][jj] = 1;
                        }
                        else
                                key_list[a[ii][jj]].push_back( ii*m+jj);
        }
        }
}

int main()
{
        citire();
        calc();

        freopen("castel.out", "w", stdout);

        printf("%d", rez);

        fclose(stdout);
        return 0;
        
}