Cod sursa(job #476886)

Utilizator dacyanMujdar Dacian dacyan Data 12 august 2010 16:12:43
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <queue>
#include <vector>
#define INF 151
using namespace std;

 ofstream fout("castel.out");

queue<pair<int,int> > Q;
pair<int,int> x;
int a[INF][INF];
bool f[INF*INF];
int m, n, K;
long sol, ip, jp;
vector<pair<int,int> > v[INF*INF]; 

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

void Read();
void Write();
void Solve();
bool OK(int i, int j);

int main()
{
   
    Read();
    Solve();
    Write();
    return 0;
}

void Read()
{
    ifstream fin("castel.in");
    fin >> m >> n >> K; 
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; j++)
                fin >> a[i][j];
    fin.close();
}

void Solve()
{
    
    int iv, jv, k, aux, ii, jj, i, j;
    if (K % n == 0) x.first = K/n;
    else x.first = K/n + 1;
    x.second = K - (x.first-1)*n; 
   
    a[x.first][x.second] = 0;
    Q.push(x);
   
    f[K] = 1;
    sol++;
    while (!Q.empty())
    {
        x = Q.front(); Q.pop();
        i = x.first;
        j = x.second;
        for ( k = 0; k < 4; ++k)
        {
            iv = i + di[k];
            jv = j + dj[k];
            if (OK(iv,jv) && f[a[iv][jv]] )
            {
                sol++;
                a[iv][jv] = 0;
                Q.push(make_pair(iv,jv));
                aux = (iv - 1)*n + jv;
                f[aux] = 1;
            }
            else
                if ( OK(iv,jv) && a[iv][jv])
                                v[a[iv][jv]].push_back(make_pair(iv,jv));
        }
	  aux = (i-1)*n + j;
      for ( k = 0; k < v[aux].size(); ++k)
        {
            ii = v[aux][k].first; jj = v[aux][k].second;
            if ( a[ii][jj] ) 
            {
                        a[ii][jj] = 0;
                        sol++;
                        f[(ii-1)*n + jj] = 1;
                        Q.push(make_pair(ii, jj));
            }    
        }
    }   
}        
                 
bool OK(int i, int j)
{
    return i > 0 && j > 0 && i <= m && j <= n;
}    
    
void Write()
{
	
    fout << sol << '\n';
    fout.close();
}