Task_M

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

struct Point{
    short x;
    short y;
    short weight;

    bool operator==(const Point& item) const{
        return item.x == x && item.y == y;
    }

    bool operator!=(const Point& item) const{
        return item.x != x || item.y != y;
    }
};

namespace std{
    template <> struct hash<Point> {
        std::size_t operator()(const Point& id) const noexcept {
            return std::hash<int>()(id.x ^ (id.y << 16));
        }
    };
}
std::vector<std::vector<Point>> graph;
short n, m;
short answer = -1;



bool inBounds(short inX, short inY){
    return (0 <= inX) && (inX < n) && (0 <= inY) && (inY < m);
}

bool passable(Point point){
    return point.weight != -1;
}

std::vector<Point> neighbours(Point point){
    std::vector<Point> result = {};
    int tempX = point.x;
    short tempY = point.y;
    if (inBounds(tempX-1, tempY) && passable(point)){
        result.push_back(graph[tempX-1][tempY]);
    }
    if (inBounds(tempX, tempY-1) && passable(point)){
        result.push_back(graph[point.x][tempY-1]);
    }
    if (inBounds(tempX+1, tempY) && passable(point)){
        result.push_back(graph[tempX+1][tempY]);
    }
    if (inBounds(tempX, tempY+1) && passable(point)){
        result.push_back(graph[tempX][tempY+1]);
    }
    return result;
}



short charToWeight(char input){
    switch (input){
        case '.':
            return 1;
        case 'W':
            return 2;
        case '#':
            return -1;
        default:
            return 0;
    }
}

struct customComparator{
    bool operator()(std::pair<short, Point> p1, std::pair<short, Point> p2){
        return p1.first < p2.first;
    }
};

template<typename T, typename priority_t>
struct PriorityQueue{
    typedef std::pair<priority_t, T> elWithPrior;
    std::priority_queue<elWithPrior, std::vector<elWithPrior>, customComparator> elements;

    inline bool empty(){
        return elements.empty();
    }

    inline void put(T item, priority_t prior){
        elements.emplace(prior, item);
    }
    T get(){
        T item = elements.top().second;
        elements.pop();
        return item;
    }
};

std::vector<Point> path(Point start, Point end, std::unordered_map<Point, Point> cameFrom){
    std::vector<Point> path;
    Point current = end;
    path.push_back(end);
    while (current != start){
        current = cameFrom[current];
        path.push_back(current);
    }
    std::reverse(path.begin(), path.end());
    return path;
}

void coorToOut(Point prev, Point cur){
    if (prev.x - cur.x < 0){
        std::cout << "S";
    } else if (prev.x - cur.x > 0){
        std::cout << "N";
    }
    if (prev.y - cur.y < 0){
        std::cout << "E";
    } else if (prev.y - cur.y > 0){
        std::cout << "W";
    }
}

int main() {
    //Ввод данных
    short x1, y1, x2, y2;
    std::cin >> n >> m >> x1 >> y1 >> x2 >> y2;


    for (short i = 0; i < n; i++){
        std::vector<Point> tempVec = {};
        for (short j = 0; j < m; j++){
            char temp;
            std::cin >> temp;
            tempVec.push_back({i,j, charToWeight(temp)});
        }
        graph.push_back(tempVec);
    }
    Point goal = graph[x2 - 1][y2 - 1];

    //Тело программы
    PriorityQueue<Point, short> startPoint;
    startPoint.put(graph[x1-1][y1-1], 0);
    std::unordered_map<Point, Point> cameFrom;
    std::unordered_map<Point, short> costSoFar;
    cameFrom[graph[x1-1][y1-1]] = graph[x1-1][y1-1];
    costSoFar[graph[x1-1][y1-1]] = 0;

    while (!startPoint.empty()){
        auto cur = startPoint.get();

        if (cur == goal){
            break;
        }
        std::vector<Point> temp = neighbours(cur);
        for (auto next : temp){
            short newCost = costSoFar[cur] + next.weight;
            if (!costSoFar.count(next) || newCost < costSoFar[next]){
                costSoFar[next] = newCost;
                cameFrom[next] = cur;
                startPoint.put(next, newCost);
            }
        }
    }
    std::vector<Point> answerVec = path(graph[x1-1][y1-1], goal, cameFrom);

    answer = answerVec.size();
    //Вывод программы
    std::cout << answer << std::endl;
    for (short i = 0; i < answerVec.size(); i++){
//        if (i != 0){
//            coorToOut(answerVec[i-1], answerVec[i]);
//        }
        std::cout << "( " << answerVec[i].x << " , " << answerVec[i].y << ")" << std::endl;
    }

    return 0;
}