Cod sursa(job #59948)

Utilizator SpiriSpiridon Alexandru Spiri Data 11 mai 2007 13:14:05
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
#define MAX 151

FILE* fin = fopen("castel.in", "r");
FILE* fout = fopen("castel.out", "w");

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

int n, m, k, a[MAX][MAX];
int c1[MAX][MAX];
int s[MAX*MAX];

int OK(int i, int j);

int main()
{
    fscanf(fin,"%d%d%d", &n, &m, &k);
    for ( int i = 1; i <= n; i++ )
    {
        for ( int j = 1; j <= m; j++ )
        {
            fscanf(fin,"%d", &a[i][j]);
        }    
    }    
    s[k] = 1;
    int c;
    int l;
    if ( k % m == 0 )
    {
        c = m;
        l = k / m;
    }    
    else
    {
        c = k % m;
        l = k / m + 1;
    }  
    s[a[l][c]] = 1; 
    c1[l][c] = 1;
    deque<pair<int,int> > q;
    q.push_back(make_pair(l,c));
    bool ok = true;
    
    while ( ok )
    {
        ok = false;
        for ( int x = 0; x < q.size(); x++ )
        {
            int i = q[x].first;
            int j = q[x].second;
            for ( int d = 0; d < 4; d++ )
            {
                int iv = i + di[d];
                int jv = j + dj[d];
                if ( OK(iv,jv) && !c1[iv][jv] )
                {
                    c1[iv][jv] = 1;
                    ok = true;
                    s[a[iv][jv]] = 1;
                    q.push_back(make_pair(iv,jv));
                }    
            }    
        }    
    }    
    
    fprintf(fout,"%d", q.size());
    
    fclose(fin);
    fclose(fout);

    return 0;
} 

int OK(int i, int j)
{
    if ( i < 1 || i > n || j < 1 || j > m ) return 0;
    int nr = m*(i-1);
    nr += j;
    if ( s[nr] == 0 && s[a[i][j]] == 0 ) return 0;
    s[nr] = 1;
    return 1;
}