Cod sursa(job #58703)

Utilizator mariusdrgdragus marius mariusdrg Data 6 mai 2007 22:17:25
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include<stdio.h>
#include<vector>
#define vi vector <int>
#define pb push_back


using namespace std;

const int maxn = 170;

int mat[maxn][maxn];
int nr;
vi vect[maxn * maxn];
int ver[maxn * maxn];
int ver1[maxn * maxn];
vi vect1[maxn * maxn];
int a[maxn][maxn];
int i;
int n;
int j;
int sol;
int m;
int st;
int st2;
int k;


void drum(int i, int j)
{
        ++sol;
        const int x[5] = {0,0,1,0,-1};
        const int y[5] = {0,1,0,-1,0};

        int o;
        int p;

        int n = vect[mat[i][j]].size();
        
        for(o = 0;o < n; ++o)
        {
                drum(vect[mat[i][j]][o],vect1[mat[i][j]][o]);
        }
        vect[mat[i][j]].clear();
        vect1[mat[i][j]].clear();
        ver[mat[i][j]] = 1;

        for(o = 1;o <= 4; ++o)
                for(p = 1;p <= 4; ++p)
                {
                        int x1 = i + x[o];
                        int y1 = j + y[o];
                        if (ver[a[x1][y1]] && !ver1[mat[x1][y1]])
                        {
                                ver1[mat[x1][y1]] = 1;
                                drum(x1,y1);
                        }
                        if (!ver[a[x1][y1]] && !ver1[mat[x1][y1]])
                        {
                                ver1[mat[x1][y1]] = 1;
                                vect[a[x1][y1]].pb(x1);
                                vect1[a[x1][y1]].pb(y1);
                        }
                }

}


int main()
{
        freopen("castel.in","r",stdin);
        freopen("castel.out","w",stdout);
        scanf("%d %d %d",&n,&m,&k);


        for(i = 1;i <= n; ++i)
                for(j = 1;j <= m; ++j)
                {
                        ++nr;
                        if (nr == k)
                        {
                                st = i;
                                st2 = j;
                        }
                        mat[i][j] = nr;
                }

        for(i = 1;i <= n; ++i)
        {
                for(j = 1;j <= m; ++j)
                {
                        scanf("%d",&a[i][j]);
                }
        }
        ver1[mat[st][st2]] = 1;
        drum(st,st2);


        printf("%d\n",sol);

        return 0;
}