#include <iostream>
using namespace std;

bool way(int curX, int curY, int x2, int y2, int n, int m, int pathPointer, int& steps, int path[], int was[][100], int labyrinth[][100]) { //cur is short for current
    if ((curX == x2) && (curY == y2)) { /*cout << "i got through with " << curX << " " << curY;*/ return true; }
    for (int i = 0; i < 4; i++) {
        switch (i){
            case 0: { //up
                if ((curY-1 >= 0) && (curY-1 < n) && (was[curX][curY-1] != 1) && (labyrinth[curX][curY-1] != 1)) {
                    steps++; path[pathPointer++] = 0; was[curX][curY-1] = 1;
                    if (way(curX, curY-1, x2, y2, n, m, pathPointer, steps, path, was, labyrinth) == true) { return true; }
                    steps--; pathPointer--;
                }
                break;
            }
            case 1: { //right
                if ((curX+1 >= 0) && (curX+1 < m) && (was[curX][curY-1] != 1) && (labyrinth[curX+1][curY] != 1)) {
                    steps++; path[pathPointer++] = 1; was[curX+1][curY] = 1;
                    if (way(curX+1, curY, x2, y2, n, m, pathPointer, steps, path, was, labyrinth) == true) { return true; }
                    steps--; pathPointer--;
                }
                break;
            }
            case 2: { //down
                if ((curY+1 >= 0) && (curY+1 < n) && (was[curX][curY+1] != 1) && (labyrinth[curX][curY+1] != 1)) {
                    steps++; path[pathPointer++] = 2; was[curX][curY+1] = 1;
                    if (way(curX, curY+1, x2, y2, n, m, pathPointer, steps, path, was, labyrinth) == true) { return true; }
                    steps--; pathPointer--;
                }
                break;
            }
            case 3: { //left
                if ((curX-1 >= 0) && (curX-1 < m) && (was[curX][curY+1] != 1) && (labyrinth[curX-1][curY] != 1)) {
                    steps++; path[pathPointer++] = 3; was[curX-1][curY] = 1;
                    if (way(curX-1, curY, x2, y2, n, m, pathPointer, steps, path, was, labyrinth) == true) { return true; }
                    steps--; pathPointer--;
                }
                break;
            }
        }
    }
}

int main()
{
    int n, m, x1, y1, x2, y2, labyrinth[100][100] = {}, path[100] = {}, steps = 0, was[100][100] = {}, pathPointer = 0;
    cout << "Enter X1 = "; cin >> x1;
    cout << "Enter Y1 = "; cin >> y1;
    cout << "Enter X2 = "; cin >> x2;
    cout << "Enter Y2 = "; cin >> y2;
    cout << "Enter N (height) = "; cin >> n;
    cout << "Enter M (length) = "; cin >> m;
    cout << "start entering the labyrinth now! 1 - blocked, 0 - free\n";
    cout << "Press space after each number, enter after each row for clarity and program stability\n";
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1;
    was[x1][y1] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> labyrinth[j][i];
        }
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << was[j][i];
        }
        cout << endl;
    }
    if (way(x1, y1, x2, y2, n, m, pathPointer, steps, path, was, labyrinth) == true) {
        for (int i = 0; i < steps; i++) {
            switch (path[i]) {
                case 0: {
                    cout << "up ";
                    break;
                }
                case 1: {
                    cout << "right ";
                    break;
                }
                case 2: {
                    cout << "down ";
                    break;
                }
                case 3: {
                    cout << "left ";
                    break;
                }
            }
        }
    } else {
        cout << "No way found!";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << was[j][i];
        }
        cout << endl;
    }
    return 0;
}