Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <queue> using namespace std; //slednite promenlivi go definiraat lavirintot. //koristime 999999 (nekoja golema vrednost) //za oznachuvanje na polinjata za koi (seushte) ne sme //go presmetale rastojanieto od pochetokot int rows = 5, cols = 5; int labyrinth[5][5] = { { 0, 999999, 999999, 999999, 999999 }, { 999999, -1, -1, 999999, 999999 }, { 999999, 999999, 999999, 999999, 999999 }, { -1, 999999, -1, -1, -1 }, { -1, 999999, 999999, 999999, 999999 } }; //pochetnata i krajnata pozicija najchesto kje ni bidat dadeni odnapred //vo ovoj primer, (0, 0) e pochetokot, a (4, 4) e krajot, t.e. ako ja vidime //matricata pogore, barame rastojanie od temeto gore-levo do ona dolu-desno int start_row = 0, start_col = 0; int end_row = 4, end_col = 4; //proveri dali odredeno pole e validno bool valid_move(pair<int, int> next) { //validno ako sme vo matricata (ne mozhe da izlezeme nadvor), i nema prechka return (next.first >= 0 && next.first < rows && next.second >= 0 && next.second < cols && labyrinth[next.first][next.second] != -1); } vector<pair<int, int> > possible_moves(pair<int, int> node) { vector<pair<int, int> > moves; moves.push_back({node.first, node.second - 1}); //odi levo moves.push_back({node.first, node.second + 1}); //odi desno moves.push_back({node.first - 1, node.second}); //odi nagore moves.push_back({node.first + 1, node.second}); //odi nadolu //ako se dozvoleni i dijagonalni dvizenja //moves.push_back({node.first - 1, node.second - 1}); //moves.push_back({node.first - 1, node.second + 1}); //moves.push_back({node.first + 1, node.second - 1}); //moves.push_back({node.first + 1, node.second + 1}); return moves; } int BFS() { queue<pair<int, int> > queue; queue.push({start_row, start_col}); while (!queue.empty()) { auto node = queue.front(); queue.pop(); vector<pair<int, int> > moves = possible_moves(node); for (auto next : moves) { if (valid_move(next)) { if (labyrinth[next.first][next.second] == 999999) { //ova e neposeteno pole queue.push(next); int distance = labyrinth[node.first][node.second] + 1; labyrinth[next.first][next.second] = distance; } } } } } int main() { BFS(); int distance = labyrinth[end_row][end_col]; cout << distance << endl; }
Input data
Program output
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!