Cod sursa(job #961128)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 17:24:45
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
 
using namespace std;
 
ifstream fin("castel.in");
ofstream fout("castel.out");
 
int d1[]={-1, +1, 0, 0};
int d2[]={0, 0, -1, 1};
int n, m, k;
int sol;
int a[152][152];
bool viz[22500], key[22500];
 
struct coada
{
    int x, y;
};
coada Q[22500];
 
int numar(int i, int j)
{
    return i * m - m + j;
}
 
void solve()
{
    bool ok = true;
    int ql, qr;
    sol = 1;
    ql = 1;
    qr = 1;
    while (ok)
    {
        ok=false;
        ql = 1;
        while (ql <= qr)
        {
            int i = Q[ql].x;
            int j = Q[ql].y;
            for (int d = 0; d < 4; ++d)
            {
                int ii = i + d1[d];
                int jj = j + d2[d];
                if (ii < 1 || jj < 1 || ii > n || j > m)
                    continue;
                if (!viz[numar(ii, jj)] && key[a[ii][jj]])
                {
                    ++qr;
                    Q[qr].x = ii;
                    Q[qr].y = jj;
                    viz[numar(ii, jj)] = true;
                    key[numar(ii, jj)] = true;
                    ok = true;
                    ++sol;
                }
            }
            ++ql;
        }
    }
}
 
int main()
{
    fin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            fin >> a[i][j];
 
    if (k % m == 0)
    {
        Q[1].x = (k - k / m) / m + 1;
        Q[1].y = m;
    }
    else
    {
        Q[1].x = (k - k % m) / m + 1;
        Q[1].y = k % m;
    }
    viz[k] = true;
    key[k] = true;
 
    solve();
 
    fout << sol;
 
    fin.close();
    fout.close();
    return 0;
}