Cod sursa(job #2878171)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 25 martie 2022 22:35:36
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
int ind_start; /// indicele celulei de start
int ma[154][154]; /// retine cheia de acces pt fiecare celula
pair<int, int> start;
int nrcel_viz;
const int dl[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};
queue<pair<int, int>> Q;
pair<int, bool> drum[154][154]; /// nr de chei cu care am ajuns in camera si daca am mai fost sau nu in acea camera
set<int> chei;
int cheie(pair<int, int> cel)
{
    return (m * (cel.first - 1) + cel.second);
}
bool inMatrice(int x, int y)
{
    return (1 <= x && x <= n && 1 <= y && y <= m);
}
void lee()
{
    drum[start.first][start.second].first = 1;
    drum[start.first][start.second].second = true;
    chei.insert(cheie(start));
    Q.push(start);
    while(!Q.empty())
    {
        int icurent = Q.front().first;
        int jcurent = Q.front().second;
        for (int d = 0; d < 4; d++)
        {
            int inou = icurent + dl[d];
            int jnou = jcurent + dc[d];
            if (inMatrice(inou, jnou) && (chei.count(ma[inou][jnou])) && ((drum[inou][jnou].second == false) || (chei.size() > drum[inou][jnou].first)))
            {
                drum[inou][jnou].second = true;
                int cheie_curent = cheie({inou, jnou});
                if (chei.count(cheie_curent))
                {
                    drum[inou][jnou].first = chei.size();
                }
                else
                {
                    drum[inou][jnou].first = chei.size() + 1;
                    chei.insert(cheie_curent);
                }
                Q.push({inou, jnou});
            }
        }
        Q.pop();
    }
}
int main()
{
    fin >> n >> m >> ind_start;
    if ((ind_start % m) == 0)
    {
        start.first = (ind_start / m);
        start.second = m;
    }
    else
    {
        start.second = (ind_start % m);
        start.first = (ind_start / m) + 1;
    }
    //fout << start.first << ' ' << start.second;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            fin >> ma[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            drum[i][j] = {0, false};
        }
    }
    lee();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if(drum[i][j].second)
            {
                nrcel_viz++;
            }
        }
    }
    fout << nrcel_viz;
    return 0;
}