Ispred dvorca, kralj ima vrt pravougaonog oblika koji je podeljen u mrežu \(n \times m\) kvadrata. Po obimu pravougaonika, kao i duž dijagonala nekih od tih kvadrata zasadio je živu ogradu i tako je napravio jedan neobičan lavirint. Napisati program koji određuje na koliko oblasti je podeljen taj lavirint (iz jedne oblasti se ne može doći u drugu ako se ne preskoči živa ograda).
Sa standardnog ulaza se učitavaju dimenzije pravougaonika \(n\) i \(m\) (\(1 \leq n, m \leq 50\)), a zatim matrica karaktera dimenzije \(n \times m\) koja opisuje pojedinačne kvadrate. Karakter \ označava da je ograda postavljena duž glavne, karakter / da je ograda postavljena duž sporedne dijagonale, a razmak da u tom kvadratu nema žive ograde.
Na standardni izlaz ispisati traženi broj oblasti.
2 2 \/ /\
4
Lavirint i njegove četiri oblasti su prikazani na slici.
2 3 /\/ /
4
Lavirint i njegove četiri oblasti su prikazani na slici.
Prilično je jasno da se zadatak može rešiti tako što se prebroje komponente povezanosti u grafu koji gradimo na osnovu podataka o lavirintu, međutim, prvo treba na pravi način definisati taj graf. Jedan način je da svaki kvadrat u lavirintu podelimo na četiri oblasti i da svaka oblast predstavlja jedan čvor grafa (taj graf ima \(4 n m\) čvorova).
Oblasti u jednom kvadratu su povezane, osim ako je postavljena neka živa ograda.
Mogući su prelasci i iz jednog u drugi kvadrat.
Na narednoj slici prikazana je povezanost oblasti u lavirintu koji se opisuje karakterima:
/\/ /
Odgovarajući graf je prikazan na narednoj slici.
Pošto kvadrata ima \(n \times m\), čvorova grafa ima \(4 \times n \times m\). Svaki čvor je povezan sa najviše \(3\) druga čvora, pa je ukupna složenost prebrojavanja komponenti \(O(nm)\).
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <tuple>
#include <limits>
using namespace std;
// svakom polju odgovaraju ima 4 čvora grafa
enum deo {GORE=0, DOLE, LEVO, DESNO};
class Graph {
private:
int m;
int n;
vector<string> linije;
vector<vector<vector<bool>>> posecen;
public:
Graph(int m, int n) {
this->m = m;
this->n = n;
inicijalizuj_posecen();
}
void dodaj_liniju(string linija) {
linije.push_back(linija);
}
void inicijalizuj_posecen() {
// alociramo vektor posecenosti cvorova
// na pocetku nije posecen ni jedan cvor
posecen.resize(m);
for (int i = 0; i < m; i++) {
posecen[i].resize(n);
for (int j = 0; j < n; j++) {
posecen[i][j].resize(4, false);
}
}
}
// obilazak grafa zadatog nizom stringova od cvora sa koordinatama (v0, k0, d0)
// to je cvor u vrsti v0, koloni k0 i delu d0
// poseceni cvorovi su određeni visedimenzionim nizom posecen
void dfs(int v0, int k0, int d0) {
// na steku cuvamo koordinate cvorova grafa
stack<tuple<int, int, int>> s;
s.emplace(v0, k0, d0);
posecen[v0][k0][d0] = true;
int v, k, d;
while (!s.empty()) {
// skidamo koordinate tekuceg cvora sa steka
// uzimamo vrstu, kolonu i deo elementa sa vrha steka
tie(v, k, d) = s.top();
s.pop();
// odredjujemo susede tekuceg cvora (ima ih najvise 3)
vector<tuple<int, int, int>> susedi;
// analiziramo polozaj tekuceg cvora u njegovom polju
switch(d) {
case GORE:
// levi i desni cvor tekuceg polja (ako nisu zaklonjeni preprekama)
if (linije[v][k] != '\\')
susedi.emplace_back(v, k, LEVO);
if (linije[v][k] != '/')
susedi.emplace_back(v, k, DESNO);
// donji cvor polja iznad (ako to polje postoji)
if (v > 0)
susedi.emplace_back(v-1, k, DOLE);
break;
case DOLE:
// levi i desni cvor tekuceg polja (ako nisu zaklonjeni preprekama)
if (linije[v][k] != '/')
susedi.emplace_back(v, k, LEVO);
if (linije[v][k] != '\\')
susedi.emplace_back(v, k, DESNO);
// gornji cvor polja ispod (ako to polje postoji)
if (v < m-1)
susedi.emplace_back(v+1, k, GORE);
break;
case LEVO:
// donji i gornji cvor tekuceg polja (ako nisu zaklonjeni preprekama)
if (linije[v][k] != '/')
susedi.emplace_back(v, k, DOLE);
if (linije[v][k] != '\\')
susedi.emplace_back(v, k, GORE);
// desni cvor polja levo (ako to polje postoji)
if (k > 0)
susedi.emplace_back(v, k-1, DESNO);
break;
case DESNO:
// donji i gornji cvor tekuceg polja (ako nisu zaklonjeni preprekama)
if (linije[v][k] != '\\')
susedi.emplace_back(v, k, DOLE);
if (linije[v][k] != '/')
susedi.emplace_back(v, k, GORE);
// levi cvor polja desno (ako to polje postoji)
if (k < n-1)
susedi.emplace_back(v, k+1, LEVO);
break;
}
int vs, ks, ds;
// prolazimo kroz niz suseda tekuceg cvora
for (const auto& sused : susedi) {
// pronalazimo vrstu, kolonu i deo suseda
tie(vs, ks, ds) = sused;
// neposecene susede stavljamo na stek
if (!posecen[vs][ks][ds]) {
posecen[vs][ks][ds] = true;
s.push(sused);
}
}
}
}
int prebroj_oblasti() {
int broj_oblasti = 0;
// odredjujemo broj komponenti povezanosti grafa
for (int v = 0; v < m; v++) {
for (int k = 0; k < n; k++) {
for (int d = GORE; d <= DESNO; d++) {
if (!posecen[v][k][d]) {
dfs(v, k, d);
broj_oblasti++;
}
}
}
}
return broj_oblasti;
}
};
int main() {
int m, n;
cin >> m >> n;
// na ovaj nacin praznimo bafer za ucitavanje, kako ne bismo imali
// problem sa getline
cin.ignore(numeric_limits<streamsize>::max(), '\n');
Graph *G = new Graph(m, n);
string linija;
// ucitavamo crtez lavirinta
for (int i = 0; i < m; i++) {
getline(cin, linija);
G->dodaj_liniju(linija);
}
cout << G->prebroj_oblasti() << endl;
return 0;
}