Cod sursa(job #59677)

Utilizator cos_minBondane Cosmin cos_min Data 10 mai 2007 08:55:43
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <stdio.h>
#include <fstream>
#include <vector>
using namespace std;

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

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<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);
    
    /*if ( K <= M ) ip = 1, jp = K;
    else
    {
        ip = 1;
        while ( K > M ) ip += 1, K -= M;
        jp = K;
    }  */  
    
    W[0][M] = 0;
    
    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]); 
            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][u] = ip;
    Q[1][u] = jp;
    bool ok = 1;
    
    T[ip][jp] = 1;
    l = W[ip][jp];
    
   // C.push_back(l);
    Sel[l] = 1;
    camera = 1;
    
    while ( ok == 1 && u <= M*N )
    {
        ok = 0;
        for ( int s = 1; s <= p; 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]] == 1 )
                            {
                                l = W[ivec][jvec];
                                //C.push_back(l);  
                                camera += 1;                              
                                Sel[l] = 1;
                                u += 1;
                                Q[0][u] = ivec;
                                Q[1][u] = jvec;
                                T[ivec][jvec] = 1;
                                ok = 1;
                                //break;
                            }    
                        }    
                    }    
                }    
            }    
        } 
        p = u;   
    }
    
    printf("%d", camera );    
}   

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