Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- int W, H, x1, y1, x2, y2;
- cin >> W >> H >> x1 >> y1 >> x2 >> y2;
- vector<vector<char>> g_char(H + 2, vector<char>(W + 2, '*'));
- for(int h = 1; h <= H; h++) {
- for(int w = 1; w <= W; w++) {
- char tmp;
- cin >> tmp;
- g_char[h][w] = tmp;
- }
- }
- vector<vector<int>> g(W*H + 1);
- int pos;
- for(int h = 1; h <= H; h++) {
- for (int w = 1; w <= W; w++) {
- pos = (h-1)*W + w;
- if(g_char[h][w+1] == '.') {
- g[pos].push_back(pos + 1);
- g[pos + 1].push_back(pos);
- }
- if(g_char[h+1][w] == '.') {
- g[pos].push_back(pos + W);
- g[pos + W].push_back(pos);
- }
- }
- }
- int start = (y1 - 1)*W + x1;
- queue<int> q;
- q.push(start);
- vector<bool> used (W*H + 1, false);
- vector<int> d (W*H + 1), p (W*H + 1);
- used[start] = true;
- p[start] = -1;
- while (!q.empty()) {
- int v = q.front();
- q.pop();
- for (size_t i=0; i<g[v].size(); ++i) {
- int to = g[v][i];
- if(to == v) continue;
- if (!used[to]) {
- used[to] = true;
- q.push (to);
- d[to] = d[v] + 1;
- p[to] = v;
- }
- }
- }
- int end = (y2 - 1)*W + x2;
- if(!used[end]) {
- cout << "NO\n";
- // printf("NO\n");
- }else {
- cout << "YES\n";
- vector<int> path;
- for(int v = end; v != -1; v = p[v]) {
- path.push_back(v);
- }
- reverse(path.begin(), path.end());
- int x, y;
- for(int i= 0; i < path.size(); i++) {
- y = path[i] / W + 1;
- x = path[i] % W;
- if(x == 0) {
- x = W;
- y--;
- }
- cout << x << ' ' << y << ' ';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement