Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- bool grid[1001][1001];
- int path[1000][1000][2];
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int w = 0, h = 0, x1 = 0, y1 = 0, x2 = 0, y2 = 0;
- cin >> w >> h >> x1 >> y1 >> x2 >> y2;
- for (int i = 1; i <= h; i++) {
- for (int j = 1; j <= w; j++) {
- grid[i][j] = getchar() == 46;
- }
- getchar();
- }
- queue<vector<int>> queue;
- queue.push({y2, x2});
- while (!queue.empty()) {
- auto cur = queue.front();
- queue.pop();
- int y = cur[0];
- int x = cur[1];
- grid[y][x] = false;
- if (x == x1 && y == y1) {
- cout << "YES\n";
- while (x != x2 || y != y2) {
- cout << x << " " << y << " ";
- int old_x = x, old_y = y;
- y = path[old_y][old_x][0];
- x = path[old_y][old_x][1];
- }
- cout << x << " " << y << " ";
- return 0;
- }
- if (grid[y - 1][x]) {
- queue.push({ y - 1, x});
- path[y - 1][x][0] = y;
- path[y - 1][x][1] = x;
- }
- if (grid[y + 1][x]) {
- queue.push({ y + 1, x});
- path[y + 1][x][0] = y;
- path[y + 1][x][1] = x;
- }
- if (grid[y][x - 1]) {
- queue.push({y, x - 1});
- path[y][x - 1][0] = y;
- path[y][x - 1][1] = x;
- }
- if (grid[y][x + 1]) {
- queue.push({y, x + 1});
- path[y][x + 1][0] = y;
- path[y][x + 1][1] = x;
- }
- }
- cout << "NO";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement