Cod sursa(job #2514821)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 26 decembrie 2019 21:18:49
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <vector>

using namespace std;

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

int n,m,k,i,j,a[155][155],b[155][155];
int cheie[155][155],c[2][155*155];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector< pair<int, int> > L[155*155];

int linie(int x)
{
    if (x%m != 0)
        return x/m+1;
    else
        return x/m;
}

int coloana(int x)
{
    if (x%m == 0)
        return m;
    else
        return x%m;
}

int main()
{
    fin >> n >> m >> k;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            fin >> a[i][j];
    b[linie(k)][coloana(k)] = 1;
    int p = 1; int u = 1; c[0][p] = linie(k); c[1][p] = coloana(k);
    while (p <= u)
    {
        int ic = c[0][p]; int jc = c[1][p];
        if (!cheie[ic][jc])
        {
            cheie[ic][jc] = 1;
            int val = (ic-1)*m+jc;
            for (i=0; i<L[val].size(); i++)
            {
                c[0][++u] = L[val][i].first;
                c[1][u] = L[val][i].second;
            }
        }
        for (int dir=0; dir<4; dir++)
        {
            int iv = ic+dx[dir]; int jv = jc+dy[dir];
            if (iv >= 1 && iv <= n && jv >= 1 && jv <= m && !b[iv][jv])
            {
                if (cheie[linie(a[iv][jv])][coloana(a[iv][jv])])
                {
                    b[iv][jv] = 1;
                    c[0][++u] = iv; c[1][u] = jv;
                }
                else
                {
                    b[iv][jv] = 1;
                    L[a[iv][jv]].push_back(make_pair(iv, jv));
                }
            }
        }
        p++;
    }
    int sol = 0;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
            if (cheie[i][j])
                sol++;
    fout << sol;
    return 0;
}