#include <iostream>
#include <vector>
using namespace std;
//typedef vector<vector<bool>> Matrica;
template<typename T>
using Matrica = vector<vector<T>>;
// funkcija koja kreira matricu postavljenu na false
Matrica<bool> napraviMatricu(int m, int n, bool value){
Matrica<bool> mat;
for(int i=0; i<m; i++){
vector<bool> tekuce;
for(int j=0; j<n; j++)
tekuce.push_back(value);
mat.push_back(tekuce);
}
return mat;
}


// ispituje da li postoji put kroz labirint od polja (x1, y1) do
// (x2, y2) pri cemu matrica posjecen oznacava koja su polja
// posjecena, a koja nisu
bool pronadjiPut(Matrica<bool>& labirint, Matrica<bool>& posjecen,
int x1, int y1, int x2, int y2) {
// ako se pocetno i krajnje polje poklapaju, put postoji
if (x1 == x2 && y1 == y2)
return true;
// cetiri smjera u kojima se mozemo pomjerati
int pomjeraj[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// pokusavamo pomeranja u svakom od tih smerova
for (int i = 0; i < 4; i++) {
// polje na koje se pomeramo
int x = x1 + pomjeraj[i][0], y = y1 + pomjeraj[i][1];
// ako smo na ivicama, moze da se desi da izadjemo van granica
// labirinta pa moramo provjeriti da li smo u granicama
// dimenzije labirinta
int m = labirint.size(), n = labirint[0].size();
if (x < 0 || x >= m || y < 0 || y >= n)
continue;
// ako tu nije zid i ako to polje nije posjeceno
if (labirint[x][y] && !posjecen[x][y]) {
// pomjeramo se na to polje, biljezimo da je posjeceno
posjecen[x][y] = true;
// ako od njega postoji put, onda postoji put i od polja (x1, y1)
if (pronadjiPut(labirint, posjecen, x, y, x2, y2))
return true;
}
}
// ni u jednom od 4 moguca smjera nismo uspjeli da stignemo do cilja,
// pa put ne postoji
return false;
}

// ispituje da li postoji put kroz labirint od polja (x1, y1) do
// (x2, y2)
bool pronadjiPut(Matrica<bool>& labirint,
int x1, int y1, int x2, int y2) {
// dimenzije labirinta
int m = labirint.size(), n = labirint[0].size();
// ni jedno polje osim starta do sada nije posjeceno
Matrica<bool> posjecen = napraviMatricu(m, n, false);
posjecen[x1][y1] = true;
// pokrecemo rekurzivnu pretragu od startnog polja
return pronadjiPut(labirint, posjecen, x1, y1, x2, y2);
}


int main(){
Matrica<bool> labirint = {
{false, false, false, false, false,
false, false, false, false, false,
false, false, false, false, false},
{false, true, true, true, true,
true, true, true, true, true,
true, true, true, true, false},
{false, true, false, false, false,
false, false, false, false, false,
false, false, false, false, false},
{false, true, true, true, true,
true, true, true, true, true,
true, true, true, true, false},
{false, false, false, false, false,
false, false, false, false, false,
false, false, false, true, false},
{false, true, true, true, true,
true, true, true, true, true,
true, true, true, true, false},
{false, true, false, false, false,
false, false, false, false, true,
false, false, false, false, false},
{false, true, true, true, true,
true, true, true, true, true,
true, true, true, true, false},
{false, false, false, false, false,
false, false, false, false, false,
false, false, false, false, false}};
cout << "Put izmedju polja (1,1) i (7,13) ";
cout << (pronadjiPut(labirint, 1, 1, 7, 13) ? "" : "ne ");
cout << "postoji" << endl;
return 1;
}