WayFinder

#define ushort unsigned short
#define uint unsigned int

#include <iostream>
#include <queue>
#include <stack>

const uint MAX_UINT = -1;
const short DX[4] = {1, 0, -1, 0};
const short DY[4] = {0, -1, 0, 1};
const ushort DIRECTIONS_COUNT = 4;
const ushort RIGHT = 0;
const ushort UP = 1;
const ushort LEFT = 2;
const ushort DOWN = 3;

struct Point
{
    ushort X;
    ushort Y;

  public:
    Point(ushort x, ushort y)
    {
        X = x;
        Y = y;
    }
};

inline bool operator==(const Point &point1, const Point &point2) { return point1.X == point2.X && point1.Y == point2.Y; }
inline bool operator!=(const Point &point1, const Point &point2) { return !(point1 == point2); }

using namespace std;

int main()
{
    ushort M, N, Xs, Ys, Xf, Yf;
    cin >> M >> N >> Xs >> Ys >> Xf >> Yf;
    Xs--, Ys--, Xf--, Yf--;
    Point start = Point(Xs, Ys);
    Point finish = Point(Xf, Yf);
    bool **maze = new bool *[N];
    uint **steps = new uint *[N];
    for (ushort X = 0; X < N; X++)
    {
        maze[X] = new bool[M];
        steps[X] = new uint[M];
    }
    for (ushort Y = 0; Y < M; Y++)
        for (ushort X = 0; X < N; X++)
        {
            ushort cell;
            cin >> cell;
            maze[X][Y] = cell == 1;
            steps[X][Y] = MAX_UINT;
        }
    steps[start.X][start.Y] = 0;
    queue<Point> q;
    q.push(start);
    while (!q.empty() && steps[finish.X][finish.Y] == MAX_UINT)
    {
        Point pos = q.back();
        q.pop();
        uint wayLength = steps[pos.X][pos.Y] + 1;
        for (ushort direction = 0; direction < DIRECTIONS_COUNT; direction++)
        {
            if (
                (direction == LEFT && pos.X == 0) ||
                (direction == UP && pos.Y == 0) ||
                (direction == RIGHT && pos.X + 1 == N) ||
                (direction == DOWN && pos.Y + 1 == M))
                continue;
            Point newPos = Point(pos.X + DX[direction], pos.Y + DY[direction]);
            if (maze[newPos.X][newPos.Y] && steps[newPos.X][newPos.Y] > wayLength)
            {
                steps[newPos.X][newPos.Y] = wayLength;
                q.push(newPos);
            }
        }
    }
    if (steps[finish.X][finish.Y] == MAX_UINT)
        cout << -1 << endl;
    else
    {
        ushort wayLength = steps[finish.X][finish.Y];
        cout << wayLength << endl;
        stack<Point> result;
        result.push(finish);
        Point pos = finish;
        while (pos != start)
        {
            wayLength--;
            for (ushort direction = 0; direction < DIRECTIONS_COUNT; direction++)
            {
                if ((direction == LEFT && pos.X == 0) ||
                    (direction == UP && pos.Y == 0) ||
                    (direction == RIGHT && pos.X + 1 == N) ||
                    (direction == DOWN && pos.Y + 1 == M))
                    continue;
                Point newPos = Point(pos.X + DX[direction], pos.Y + DY[direction]);
                if (maze[newPos.X][newPos.Y] && steps[newPos.X][newPos.Y] == wayLength)
                {
                    result.push(pos = newPos);
                    break;
                }
            }
        }
        while (!result.empty())
        {
            Point cell = result.top();
            result.pop();
            cout << cell.X + 1 << ' ' << cell.Y + 1 << endl;
        }
    }
    delete[] maze;
    delete[] steps;
    return 0;
}