Cod sursa(job #59846)

Utilizator cos_minBondane Cosmin cos_min Data 10 mai 2007 18:41:21
Problema Castel Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
// Castel
#include <stdio.h>
#include <fstream>
#include <vector>
#include <iostream>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

#define in "castel.in"
#define out "castel.out"
#define dim 151

hash_map<int,bool> Sel;
int A[dim][dim], W[dim][dim];
bool T[dim][dim];
int N, M, K;
//int Q[2][dim*dim];
int ip, jp, ivec, jvec;
//bool Sel[dim*dim];
int camera = 0;
vector< vector<int> > Q; 
//vector<int> C;

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

void ReadData();
void Solve();
int Ok(int,int);

int main()
{
    ReadData();
    Solve();
    
    return 0;
}    

void ReadData()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);

    scanf("%d%d%d", &N, &M, &K);
   // cin >> N >> M >> K;
    
    W[0][M] = 0;
    Q.resize(2);
    
    for ( int i = 1; i <= N; i++ )
    {
        W[i][0] = W[i-1][M];
        for ( int j = 1; j <= M; j++ )
        {
            scanf("%d", &A[i][j]); 
           // cin >> A[i][j];
            W[i][j] = W[i][j-1] + 1;
            if ( W[i][j] == K ) ip = i, jp = j;
            T[i][j] = 0;
        }
    }       
}   

void Solve()
{
    int p, u, i, j, l;
    p = u = 1;
    Q[0].push_back(ip);    
    Q[1].push_back(jp);
    bool ok = 1;
    
    T[ip][jp] = 1;
    l = W[ip][jp];
    Sel[l] = 1;
   
   // C.push_back(l);
    
    camera = 1;
    
    while ( ok == 1 )
    {
        ok = 0;
        for ( int s = 0; s < u; s++ )
        {
            i = Q[0][s];
            j = Q[1][s];
            
            for ( int dir = 0; dir < 4; dir++ )
            {
                ivec = i + di[dir];
                jvec = j + dj[dir];
                
                if ( Ok(ivec,jvec) )
                {
                    if ( !T[ivec][jvec] )
                    {
                      // for ( int x = 0; x < C.size(); x++ )
                       {
                          // if ( A[ivec][jvec] == C[x] )
                           if ( Sel[A[ivec][jvec]] )
                           {
                               
                                l = W[ivec][jvec];
                                camera += 1;                              
                                //C.push_back(l);
                                if ( !Sel[l] ) Sel[l] = 1;
                                u += 1;
                                Q[0].push_back(ivec);
                                Q[1].push_back(jvec);
                                T[ivec][jvec] = 1;
                                ok = 1;
                                break;
                         }   
                       }          
                    }    
                }    
            }    
        } 
        p = u;
    }
    
    printf("%d", Q[0].size() );    
   // cout << camera;
}   

int Ok(int i, int j)
{
    if ( i < 1 || i > N || j < 1 || j > M ) return 0;
    return 1;
}