Cod sursa(job #2724102)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 16 martie 2021 14:48:44
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 150
#define MMAX 150

using namespace std;

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

int n, m, k;

bool f[NMAX * MMAX + 1];
int ch[NMAX + 2][MMAX + 2];
int d[NMAX + 2][MMAX + 2];
vector<pair<int, int> >v;
int gx[4] = {-1, 0, 0, 1};
int gy[4] = {0, -1, 1, 0};

void lee (int xStart, int yStart){
    cout << xStart << ' ' << yStart << '\n';

    v.push_back({xStart, yStart});
    d[xStart][yStart] = 1;
    f[ (xStart - 1) * m + yStart ] = 1;

    int vizCamere = 1;
    while(vizCamere){ //cat timp parcurgerea drumului a rezultat la descoperirea a minim unei noi camere

        vizCamere = 0;
        int i = 0;
        while(i < v.size()){
            int x = v[i].first;
            int y = v[i].second;

            for(int i = 0; i < 4; i++){
                int xn = x + gx[i];
                int yn = y + gy[i];

                if(d[xn][yn] == 0 && f[ ch[xn][yn] ] == 1){ //daca e nevizitat si pot sa intru cu cheile pe care le am momentan
                    vizCamere = 1; //am vizitat minim o camera
                    d[xn][yn] = d[x][y] + 1;

                    //marchez ca am obtinut cheia ce se afla in camera asta
                    f[ (xn - 1) * m + yn ] = 1;

                    v.push_back({xn, yn});
                }

            }

            i++;
            //cd.pop_front();
        }
    }


}

void Bordare(){
    for(int i = 0; i <= n + 1; i++){
        d[i][0] = d[i][m + 1] = 1;
    }
    for(int j = 0; j <= m + 1; j++){
        d[0][j] = d[n + 1][j] = 1;
    }
}



int main()
{
    fin >> n >> m >> k;
    Bordare();

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            fin >> ch[i][j];
        }
    }

    lee((k - 1) / m + 1, (k - 1) % m + 1);


    int nrCamere = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(d[i][j] > 0){
                nrCamere++;
            }
        }
    }
    fout << nrCamere;

    return 0;
}