Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <queue>
- struct Point {
- int x, y;
- void add(const Point& p) {
- x += p.x;
- y += p.y;
- }
- bool operator ==(const Point& p) const {
- return (x == p.x && y == p.y);
- }
- };
- bool passable(const Point& p, const std::vector<std::string>& v) {
- const char PASSABLE = '.';
- const std::size_t SIZE = v.size();
- //Bound Check
- if (p.x < 0 || p.y < 0 || p.x >= SIZE || p.y >= SIZE)
- return false;
- return v[p.x][p.y] == PASSABLE;
- }
- int getMinimumMoves(std::vector<std::string> grid, int startX, int startY, int endX, int endY)
- {
- const Point START{ startX, startY };
- const Point END { endX, endY};
- const std::size_t N = grid.size();
- const Point DIRECTIONS[4] = {
- { 0,-1 }, //NORTH
- { 1, 0 }, //EAST
- { 0, 1 }, //SOUTH
- {-1, 0 }, //WEST
- };
- const Point SENTINEL{ -1,-1 };
- if (START == END)
- return 0;
- std::vector<bool> visited(N * N, false);
- int distance = 0;
- std::queue<Point> q;
- q.push(START);
- q.push(SENTINEL);
- visited[START.y + START.x * N] = true;
- while (!q.empty()) {
- const Point point = q.front();
- q.pop();
- if (point == SENTINEL && !q.empty()) {
- q.push(SENTINEL);
- distance++;
- }
- for (int i = 0; i < 4; i++) {
- for (Point p = point; passable(p, grid); p.add(DIRECTIONS[i])) {
- if (p == END)
- return ++distance;
- else if (!visited[p.x + p.y * N]) {
- visited[p.x + p.y * N] = true;
- q.push(p);
- }
- }
- }
- }
- return -1;
- }
- int main(int argc, char** argv)
- {
- ////вход
- unsigned N;
- std::vector<std::string> grid;
- Point start, end;
- std::cin >> N;
- std::string buffReader;
- grid.reserve(N);
- buffReader.reserve(N);
- for (int i = 0; i < N; i++) {
- std::cin >> buffReader;
- grid.push_back(buffReader);
- }
- std::cin >> start.x >> start.y
- >> end.x >> end.y;
- //изход
- std::cout << getMinimumMoves(grid, start.x, start.y, end.x, end.y);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement