#include <iostream> #include <vector> #include <queue> #include <set> using namespace std; struct Position { int x, y, moves; }; int minimumMoves(const vector<string>& grid, int startX, int startY, int goalX, int goalY) { int n = grid.size(); vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Right, Down, Left, Up queue<Position> q; set<pair<int, int>> visited; q.push({startX, startY, 0}); visited.insert({startX, startY}); while (!q.empty()) { Position current = q.front(); q.pop(); // Check if we reached the goal if (current.x == goalX && current.y == goalY) { return current.moves; } // Explore in all four directions for (auto& dir : directions) { int nx = current.x, ny = current.y; // Move until hitting a boundary or a blocked cell while (nx + dir.first >= 0 && nx + dir.first < n && ny + dir.second >= 0 && ny + dir.second < n && grid[nx + dir.first][ny + dir.second] == '.') { nx += dir.first; ny += dir.second; // If we reach the goal during the movement if (nx == goalX && ny == goalY) { return current.moves + 1; } // If this position hasn't been visited if (visited.find({nx, ny}) == visited.end()) { visited.insert({nx, ny}); q.push({nx, ny, current.moves + 1}); } } } } // If we exit the loop without having found the goal return -1; // Return -1 if the goal is unreachable } int main() { int n; cin >> n; vector<string> grid(n); for (int i = 0; i < n; ++i) { cin >> grid[i]; } int startX, startY, goalX, goalY; cin >> startX >> startY >> goalX >> goalY; cout << minimumMoves(grid, startX, startY, goalX, goalY) << endl; return 0; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter