#include #include using namespace std; class Heap { vector> data; void shift_up(int i) { int p = (i - 1) / 2; if (data[p] > data[i]) { swap(data[p], data[i]); shift_up(p); } } void shift_down(int i) { int left = i * 2 + 1; int right = i * 2 + 2; if (left >= data.size()) { return; } int to_swap = left; if (right < data.size()) { if (data[right] < data[left]) { to_swap = right; } } if (data[to_swap] < data[i]) { swap(data[i], data[to_swap]); shift_down(to_swap); } } public: void push(int priority, int index) { data.push_back(make_pair(priority, index)); shift_up(data.size() - 1); } void pop() { swap(data[0], data[data.size() - 1]); data.pop_back(); shift_down(0); } int top() { return data[0].second; } bool empty() { return data.empty(); } }; int main() { int N, M; cin >> N >> M; int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--; x2--; y2--; vector A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } vector weight(N*M); vector> graph(N*M); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { int x = i * M + j; if (i > 0 && A[i-1][j] != '#') { graph[x].push_back(x - M); } if (j > 0 && A[i][j-1] != '#') { graph[x].push_back(x - 1); } if (i < N - 1 && A[i+1][j] != '#') { graph[x].push_back(x + M); } if (j < M - 1 && A[i][j+1] != '#') { graph[x].push_back(x + 1); } if (A[i][j] == '.') { weight[x] = 1; } else if (A[i][j] == 'W') { weight[x] = 2; } } } vector colors(N*M); vector length(N*M); vector parent(N*M, -1); Heap q; int x = x2 * M + y2; q.push(0, x); colors[x] = 1; parent[x] = x; while (!q.empty()) { int u = q.top(); q.pop(); for (int v : graph[u]) { if (colors[v] == 0) { colors[v] = 1; length[v] = length[u] + weight[v]; parent[v] = u; q.push(length[v], v); } } } int y = x1 * M + y1; if (parent[y] == -1) { cout << -1; return 0; } cout << length[y] << '\n'; int t = y; while (t != parent[t]) { int q = parent[t] - t; if (q == M) { cout << "S"; } if (q == -M) { cout << "N"; } if (q == 1) { cout << "E"; } if (q == -1) { cout << "W"; } t = parent[t]; } return 0; }