Cod sursa(job #2353990)

Utilizator MattCMatei Coroiu MattC Data 24 februarie 2019 19:33:10
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int mat[155][155];
int v[155][155];
int fr[155 * 155];

queue < pair < int, int > > q;

bool ok(int i, int j)
{
    return (i >= 1 && j >= 1 && i <= n && j <= m && fr[mat[i][j]]);
}

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

int main()
{
    int cnt = 0, k, poz1, poz2, i, j, ii, jj, K, nr = 0;

    fin >> n >> m >> k;

    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
        {
            fin >> mat[i][j];
            v[i][j] = ++cnt;
            if (cnt == k)
                poz1 = i, poz2 = j;
        }
    }

    q.push(make_pair(poz1, poz2));
    fr[k] = 1;

    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (K = 0; K < 4; ++K)
        {
            ii = i + di[K];
            jj = j + dj[K];
            if (ok(ii, jj))
            {
                if (!fr[v[ii][jj]])
                {
                    nr = 0;
                    fr[v[ii][jj]] = 1;
                    q.push(make_pair(ii, jj));
                }
                else ++nr, q.push(make_pair(ii, jj));
                if (nr == 22500)
                {
                    cnt = 0;
                    for (i = 1; i <= n * m; ++i)
                    {
                        if (fr[i])
                            ++cnt;
                    }
                    fout << cnt << '\n';
                    return 0;
                }
            }
        }
    }

    return 0;
}