Cod sursa(job #3001084)

Utilizator dariustgameTimar Darius dariustgame Data 13 martie 2023 11:00:47
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

int n, m, k;
bool chei[23000];
int cam[152][152];
int lee[152][152];

struct pos
{
    int x, y;
};

queue<pos> leePos;
vector<pos> close[23000];

int poz[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void solve()
{
    while (!leePos.empty())
    {
        pos primu = leePos.front();
        int cheie = (primu.x - 1) * m + primu.y;
        lee[primu.x][primu.y] = -1;
        chei[cheie] = 1;
        for (int i = 0; i < close[cheie].size(); i++)
        {
            if (lee[close[cheie][i].x][close[cheie][i].y] != 1)
            {
                leePos.push(close[cheie][i]);
                lee[close[cheie][i].x][close[cheie][i].y] = 1;
            }
        }
        leePos.pop();
        for (int i = 0; i < 4; i++)
        {
            int x, y;
            x = primu.x + poz[i][0];
            y = primu.y + poz[i][1];
            if (x < 1 || y < 1 || x > n || y > m) continue;
            if (lee[x][y] != -1 && chei[cam[x][y]])
            {
                leePos.push({x, y});
            }
            else if (lee[x][y] != -1)
            {
                close[cam[x][y]].push_back({x, y});
            }
        }
    }
}

int main()
{
    fin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            fin >> cam[i][j];
        }
    }
    int x = (k - 1) / m + 1;
    int y = (k - 1) % m + 1;
    leePos.push({x, y});
    lee[x][y] = -1;
    chei[k] = 1;
    solve();
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (lee[i][j] == -1)
                cnt++;
        }
    }
    fout << cnt;
    return 0;
}