// Labyrinthv2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
using namespace std;

void varInput(int& x1, int& y1, int& x2, int& y2, int& h, int& l, int labyrinth[][100]) {
    cout << "Enter X1 = "; cin >> x1;
    cout << "Enter Y1 = "; cin >> y1;
    cout << "Enter X2 = "; cin >> x2;
    cout << "Enter Y2 = "; cin >> y2;
    cout << "Enter H (height) = "; cin >> h;
    cout << "Enter L (length) = "; cin >> l;
    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;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < l; j++) {
            cin >> labyrinth[j][i];
        }
    }
}

void output(int path[], int steps, bool possible) {
    if (possible == 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!";
    }
}

bool way(int curX, int curY, int finX, int finY, int h, int l, int& pathPointer, int path[], int was[][100], int labyrinth[][100]) { //cur is short for current
    if ((curX == finX) && (curY == finY)) { return true; }
    //lol
    if ((curY - 1 >= 0) && (curY - 1 < h) && (was[curX][curY - 1] != 1) && (labyrinth[curX][curY - 1] != 1)) { //up
        path[pathPointer++] = 0; was[curX][curY - 1] = 1;
        if (way(curX, curY - 1, finX, finY, h, l, pathPointer, path, was, labyrinth) == true) { return true; }
        pathPointer--;
    }
    //lol
    if ((curX + 1 >= 0) && (curX + 1 < l) && (was[curX + 1][curY] != 1) && (labyrinth[curX + 1][curY] != 1)) { //right
        path[pathPointer++] = 1; was[curX + 1][curY] = 1;
        if (way(curX + 1, curY, finX, finY, h, l, pathPointer, path, was, labyrinth) == true) { return true; }
        pathPointer--;
    }
    //lol
    if ((curY + 1 >= 0) && (curY + 1 < h) && (was[curX][curY + 1] != 1) && (labyrinth[curX][curY + 1] != 1)) { //down
        path[pathPointer++] = 2; was[curX][curY + 1] = 1;
        if (way(curX, curY + 1, finX, finY, h, l, pathPointer, path, was, labyrinth) == true) { return true; }
        pathPointer--;
    }
    //lol
    if ((curX - 1 >= 0) && (curX - 1 < l) && (was[curX - 1][curY ] != 1) && (labyrinth[curX - 1][curY] != 1)) { //left
        path[pathPointer++] = 3; was[curX - 1][curY] = 1;
        if (way(curX - 1, curY, finX, finY, h, l, pathPointer, path, was, labyrinth) == true) { return true; }
        pathPointer--;
    }
    return false;
}


int main()
{
    int h, l, x1, y1, x2, y2, labyrinth[100][100] = {}, path[100] = {}, was[100][100] = {}, pathPointer = 0;
    varInput(x1, y1, x2, y2, h, l, labyrinth); was[x1][y1] = 1;
    bool possible = way(x1, y1, x2, y2, h, l, pathPointer, path, was, labyrinth);
    output(path, pathPointer, possible);
    return 0;
}