Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ο»Ώ#include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <climits>
- #include <string>
- #include <set>
- #include <cmath>
- #include <map>
- #include <unordered_map>
- #include <numeric>
- #include <random>
- #include <memory>
- #include <chrono>
- #include <iterator>
- #include <functional>
- #include <unordered_set>
- #include <cassert>
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(x...)
- #endif
- //#pragma GCC optimize("Ofast")
- //#define int ll
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair < int, int > pii;
- typedef pair < ll, ll > pll;
- #define sz(x) int((x).size())
- #ifndef LOCAL
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(228);
- #endif
- const int N = 1e3 + 7;
- const int inf = INT_MAX / 2;
- const ll INF = LLONG_MAX / 3;
- const int MOD = 1e9 + 7;
- const double eps = 1e-6;
- const string cars[] = {"π", "π", "π"};
- struct Node {
- int x, y, l, w;
- bool check() {
- return (--l) <= 0;
- }
- };
- int n, m, sx, sy, fx, fy, d[N][N];
- char a[N][N];
- short used[N][N];
- queue < Node > q;
- pii p[N][N];
- void go(int x, int y, int px, int py) {
- if (x >= 1 && x <= n && y >= 1 && y <= m && !used[x][y] && a[x][y] != '#') {
- used[x][y] = 1;
- if (a[x][y] == '.') {
- q.push({ x, y, 1, d[px][py] + 1 });
- p[x][y] = { px, py };
- }
- else {
- q.push({ x, y, 2, d[px][py] + 2 });
- p[x][y] = { px, py };
- }
- }
- }
- void bfs() {
- q.push({ sx, sy, 0, 0 });
- used[sx][sy] = 1;
- while (!q.empty()) {
- auto u = q.front();
- q.pop();
- if (u.check()) {
- d[u.x][u.y] = u.w;
- go(u.x + 1, u.y, u.x, u.y);
- go(u.x - 1, u.y, u.x, u.y);
- go(u.x, u.y + 1, u.x, u.y);
- go(u.x, u.y - 1, u.x, u.y);
- }
- else {
- q.push(u);
- }
- }
- }
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(4);
- ios::sync_with_stdio(false);
- cin.tie();
- cout.tie();
- cin >> n >> m >> sx >> sy >> fx >> fy;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- cin >> a[i][j];
- }
- }
- bfs();
- if (!used[fx][fy]) {
- return cout << "-1", 0;
- }
- cout << d[fx][fy] << "\n";
- vector < pii > path;
- for (pii i = { fx, fy }; i != pii{ sx, sy }; i = p[i.first][i.second]) {
- path.push_back(i);
- }
- path.push_back({ sx, sy });
- reverse(path.begin(), path.end());
- for (int i = 1; i < sz(path); i++) {
- int dx = path[i].first - path[i - 1].first;
- int dy = path[i].second - path[i - 1].second;
- if (dx == 1) {
- cout << 'S';
- }
- else if (dx == -1) {
- cout << 'N';
- }
- else if (dy == 1) {
- cout << 'E';
- }
- else {
- cout << 'W';
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement