Cod sursa(job #2534771)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 30 ianuarie 2020 22:10:50
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

int n, m, k, i, j;
int usa[151][151];

int cheie[151][151], c;
bool cheie_gasita[22501];

bool u[152][152], u1[22501];

int rez;

int dx[4] = {1, -1, 0,  0};
int dy[4] = {0,  0, 1, -1};

int main()
{
    f >> n >> m >> k;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            f >> usa[i][j];
            cheie[i][j] = ++c;
        }


    for (i=0; i<=n+1; i++)
        u[i][0] = u[i][m+1] = 1;
    for (j=0; j<=m+1; j++)
        u[0][j] = u[n+1][j] = 1;


    int poz1 = k/m + (k%m > 0);
    int poz2 = k%m + m*(k%m == 0);

    int x, y;
    int xx, yy;
    int xxx, yyy;
    bool gata=0;

    u[poz1][poz2] = 1;
    cheie_gasita[cheie[poz1][poz2]] = 1;

    queue < pair < int, int > > cu_cheie;
    vector < pair < int, int > > fara_cheie[25001];
    cu_cheie.push(make_pair(poz1, poz2));

    while (!cu_cheie.empty())
    {
        x = cu_cheie.front().first;
        y = cu_cheie.front().second;
        cu_cheie.pop();

        if (!cheie_gasita[cheie[x][y]])
        {
            cheie_gasita[cheie[x][y]] = 1;
            for (int j=0; j<fara_cheie[cheie[x][y]].size(); j++)
            {
                xx = fara_cheie[cheie[x][y]][j].first;
                yy = fara_cheie[cheie[x][y]][j].second;
                cu_cheie.push(make_pair(xx, yy));
            }
        }

        rez++;

        for (int i=0; i<4; i++)
        {
            xx = x + dx[i];
            yy = y + dy[i];
            if (!u[xx][yy])
            {
                u[xx][yy] = 1;
                if (cheie_gasita[usa[xx][yy]])
                {
                    cu_cheie.push(make_pair(xx, yy));
                    if (!cheie_gasita[cheie[xx][yy]])
                    {
                        cheie_gasita[cheie[xx][yy]] = 1;
                        for (int j=0; j<fara_cheie[cheie[xx][yy]].size(); j++)
                        {
                            xxx = fara_cheie[cheie[xx][yy]][j].first;
                            yyy = fara_cheie[cheie[xx][yy]][j].second;
                            cu_cheie.push(make_pair(xxx, yyy));
                        }
                    }
                }
                else
                    fara_cheie[usa[xx][yy]].push_back(make_pair(xx, yy));
            }
        }
    }

    g << rez;

    return 0;
}