ForMaxCivilization

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;


void dijsktra(int xst, int yst, vector<vector<int>> &map,vector<vector<int>> &weights, vector<vector<bool>> &visited) {

    weights[xst][yst] = 0;
    priority_queue<pair<int, pair<int, int>>> dots;
    dots.push(make_pair(0, make_pair(xst, yst)));

    while (!dots.empty()) {
        int x = dots.top().second.first;
        int y = dots.top().second.second;
        dots.pop();

        if (visited[x][y]) {
            continue;
        }

        visited[x][y] = true;

        if (x > 0 && !visited[x-1][y] && map[x-1][y] != -1) {
            if (weights[x][y] + map[x-1][y] < weights[x-1][y]) {
                weights[x-1][y] = weights[x][y] + map[x-1][y];
            }
            dots.push(make_pair(-weights[x-1][y], make_pair(x-1, y)));
        }

        if (x < map.size() - 1 && !visited[x+1][y] && map[x+1][y] != -1) {
            if (weights[x][y] + map[x+1][y] < weights[x+1][y]) {
                weights[x+1][y] = weights[x][y] + map[x+1][y];
            }
            dots.push(make_pair(-weights[x+1][y], make_pair(x+1, y)));
        }

        if(y > 0 && !visited[x][y-1] && map[x][y-1] != - 1) {
            if (weights[x][y] + map[x][y-1] < weights[x][y-1]) {
                weights[x][y-1] = weights[x][y] + map[x][y-1];
            }
            dots.push(make_pair(-weights[x][y-1], make_pair(x, y-1)));
        }

        if (y < map[0].size() - 1 && !visited[x][y+1] && map[x][y+1] != -1) {
            if (weights[x][y] + map[x][y+1] < weights[x][y+1]) {
                weights[x][y+1] = weights[x][y] + map[x][y+1];
            }
            dots.push(make_pair(-weights[x][y+1], make_pair(x, y+1)));
        }
    }
}

void printDirection(int x, int y, vector<vector<int>> &weights) {

    int minWeight;
    if (weights[x][y] == 0) {
        return;
    } else {
        minWeight = weights[x][y];
    }

    char dir;
    if (x > 0 && minWeight > weights[x-1][y]) {
        minWeight = weights[x-1][y];
        dir = 'S';
    }
    if (x < weights.size() - 1 && minWeight > weights[x+1][y]) {
        minWeight = weights[x+1][y];
        dir = 'N';
    }
    if (y > 0 && minWeight > weights[x][y-1]) {
        minWeight = weights[x][y-1];
        dir = 'E';
    }
    if (y < weights[0].size() - 1 && minWeight > weights[x][y+1]) {
        minWeight = weights[x][y+1];
        dir = 'W';
    }

    if (dir == 'S') {
        printDirection(x-1, y, weights);
    } else if (dir == 'N') {
        printDirection(x+1, y, weights);
    } else if (dir == 'E') {
        printDirection(x, y-1, weights);
    } else if (dir == 'W') {
        printDirection(x, y+1, weights);
    }

    cout << dir;
}

int main() {
    ifstream file("input.txt");

    int n, m, xbeg, ybeg, xfin, yfin;
    file >> n >> m >> xbeg >> ybeg >> xfin >> yfin;

    vector<vector<int>> map(n, vector<int>(m, -1));
    vector<vector<int>> weights(n, vector<int>(m, INT32_MAX));
    vector<vector<bool>> visited(n, vector<bool>(m, false));


    char s;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            file >> s;
            if (s == '.') {
                map[i][j] = 1;
            } else if (s == 'W') {
                map[i][j] = 2;
            } else if (s == '#') {
                map[i][j] = -1;
            }
        }
    }

    dijsktra(xbeg - 1, ybeg - 1, map, weights, visited);

    if (weights[xfin-1][yfin-1] == INT32_MAX) {
        cout << -1;
    } else {
        cout << weights[xfin-1][yfin-1] << endl;
        printDirection(xfin-1, yfin-1, weights);
    }

    file.close();
    return 0;
}