Cod sursa(job #3219463)

Utilizator Allie28Radu Alesia Allie28 Data 31 martie 2024 14:32:07
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <queue>
#include <unordered_map>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");

const int LMAX = 155;

int n, m;

bool inside(int i, int j) {
    return i > 0 && i <= n && j > 0 && j <= m;
}

int dx[5] = {1, 0, -1, 0}, dy[5] = {0, 1, 0, -1};
vector<int> posrooms[24025];
int a[LMAX][LMAX], ans;
bool key[24025], viz[24025];
queue<int> Q;

void findrooms(int next) {
    while (posrooms[next].size() > 0) {
        int room = posrooms[next].back();
        key[room] = true;
        ans++;
        Q.push(room);
        findrooms(room);
        posrooms[next].pop_back();
    }
}

void bfs(int k) {
    Q.push(k);
    key[k] = true;
    ans++;
    viz[k] = true;
    while (!Q.empty()) {
        int room = Q.front();
        Q.pop();
        int i, j;
        i = (room - 1)/m + 1;
        j = (room - 1)%m + 1;
        int l, c, next;
        for (int dir = 0; dir < 4; dir++) {
            l = i + dy[dir];
            c = j + dx[dir];
            next = c + (l-1)*m;
            //fout<<next<<" ";
            if (inside(l, c) && !viz[next]) {
                if (key[a[l][c]]) { //daca am cheie pt vecin
                    key[next] = true;
                    ans++;
                    findrooms(next);
                    Q.push(next); //este posibila
                }
                else if (!viz[next]){ //nu am cheie pt asta momentan
                    posrooms[a[l][c]].push_back(next);//adaug camerele care s ar putea deschide daca capat cheia respectiva
                }
                viz[next] = 1;
            }
        }
    }
}

int main() {
    int k, i, j;
    fin>>n>>m>>k;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            fin>>a[i][j];
        }
    }
    bfs(k);
    fout<<ans;



    fin.close();
    fout.close();
    return 0;
}