Cod sursa(job #929852)

Utilizator Ionut228Ionut Calofir Ionut228 Data 27 martie 2013 12:10:37
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

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

int n, m, k;
int c, sol;
int a[152][152];
bool key[22500], camera[22500], l[22500];

struct coada
{
    int x, y;
};
coada Q[22500], lst[22500];

void solve()
{
    int ql = 1, qr = 1;
    int lr = 0;
    sol = 1;
    while (ql <= qr)
    {
        int i = Q[ql].x;
        int j = Q[ql].y;
        for (int lista = 1; lista <= lr; ++lista)
        {
            if (l[lst[lista].x * m - m + lst[lista].y] == true)
                continue;
            if (key[lst[lista].x * m - m + lst[lista].y])
            {
                ++qr;
                Q[qr].x = lst[lista].x;
                Q[qr].y = lst[lista].y;
                if (!camera[lst[lista].x * m - m + lst[lista].y])
                {
                    ++sol;
                    key[lst[lista].x * m - m + lst[lista].y] = true;
                }
                camera[lst[lista].x * m - m + lst[lista].y] = 1;
                l[lst[lista].x * m - m + lst[lista].y] = true;
            }
        }
        for (int d = 0; d < 4; ++d)
        {
            int ii = i + di[d];
            int jj = j + dj[d];
            if (ii < 1 || jj < 1 || i > n || j > m)
                continue;
            if (key[a[ii][jj]] && !camera[ii * m - m + jj])
            {
                ++qr;
                Q[qr].x = ii;
                Q[qr].y = jj;
                ++sol;
                key[ii * m - m + jj] = true;
                camera[ii * m - m + jj] = 1;
            }
            else
            {
                ++lr;
                lst[lr].x = ii;
                lst[lr].y = jj;
            }
        }
        ++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;
        Q[1].y = k / m;
    }
    else
    {
        Q[1].x = (k - k % m) / m + 1;
        Q[1].y = k % m;
    }

    key[k] = true;
    camera[k] = 1;

    solve();

    fout << sol;

    fin.close();
    fout.close();
    return 0;
}