#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #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; }