Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <queue> using namespace std; const int MAX_RC = 101; //kje gi prochitame ovie vrednosti vo main() int rows, cols; int labyrinth[MAX_RC][MAX_RC][2]; int start_row, start_col; int object_row, object_col; int end_row, end_col; struct state { int row, col, took_object; }; //proveri dali poleto e validno za poseta bool valid_move(state next) { return (next.row >= 0 && next.row < rows && next.col >= 0 && next.col < cols && labyrinth[next.row][next.col][next.took_object] != -1); } state build_next_move(int row, int col, int previous_took_object) { state move; move.row = row; move.col = col; move.took_object = previous_took_object; if (previous_took_object == 0 && move.row == object_row && move.col == object_col) { //go nemavme predmetot prethodno, no, vo ovoj poteg, kje zastaneme //na toa pole, pa sega go imame i predmetot move.took_object = 1; } return move; } vector<state> possible_moves(state node) { vector<state> moves; moves.push_back(build_next_move(node.row, node.col - 1, node.took_object)); //odi levo moves.push_back(build_next_move(node.row, node.col + 1, node.took_object)); //odi desno moves.push_back(build_next_move(node.row - 1, node.col, node.took_object)); //odi nagore moves.push_back(build_next_move(node.row + 1, node.col, node.took_object)); //odi nadolu return moves; } int BFS() { queue<state> queue; state initial; initial.row = start_row; initial.col = start_col; initial.took_object = 0; //go nemame predmetot na pochetokot (ne sme stapnale na tretoto pole) queue.push(initial); while (!queue.empty()) { auto node = queue.front(); queue.pop(); vector<state> moves = possible_moves(node); for (auto next : moves) { if (valid_move(next)) { if (labyrinth[next.row][next.col][next.took_object] == 999999) { queue.push(next); int distance = labyrinth[node.row][node.col][node.took_object] + 1; labyrinth[next.row][next.col][next.took_object] = distance; } } } } } int main() { cout << "Enter the dimensions of the labyrinth: " << endl; cin >> rows >> cols; cout << "Enter the start location: " << endl; cin >> start_row >> start_col; cout << "Enter the location of the object: " << endl; cin >> object_row >> object_col; cout << "Enter the end location: " << endl; cin >> end_row >> end_col; //inicijaliziraj ja matricata so koja e pretstaven lavirintot for (int r=0; r < rows; r++) { for (int c=0; c < cols; c++) { labyrinth[r][c][0] = 999999; labyrinth[r][c][1] = 999999; if (r == start_row && c == start_col) { //pochetnoto pole go oznachuvame so 0 labyrinth[r][c][0] = 0; } } } int obstacles; cout << "How many obstacles are in the labyrinth: " << endl; cin >> obstacles; cout << "Enter the locations of the obstacles, one per line." << endl; for (int i=0; i < obstacles; i++) { int obstacle_row, obstacle_col; cin >> obstacle_row >> obstacle_col; labyrinth[obstacle_row][obstacle_col][0] = -1; labyrinth[obstacle_row][obstacle_col][1] = -1; } BFS(); int distance = labyrinth[end_row][end_col][1]; cout << distance << endl; }
Input data
Program output
5 5 0 0 2 1 4 4 8 1 1 1 3 2 3 3 3 3 2 3 1 3 0 4 3
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!