#include <iostream>
#include <vector>
#include <windows.h>
using namespace std;
int lastmove = 0;

// Returns true if you can reach the bottom-right (otherwise returns false).
// You can move up, down, left, or right.  You cannot move diagonally.
// 1 represents a wall.  You cannot go through a wall.
bool winnable(int maze[5][5], int m, int n) {





   //  Testing moves in right, down, left and up directions
   // If the previous move is the opposite vertically or horizontally
   // It is not valid
     cout << m << "  " << n << endl;
     cout << maze[m][n] << endl;
     Sleep(1000);



     if (n<5&& maze[m][n+1]!=1 && lastmove!=3){

        if(m==5&&n==5)
        return true;

         lastmove = 1;
         winnable(maze,  m,  ++n);
    }
     if (m<5&&maze[m+1][n]!=1 && lastmove!=4){

        if(m==5&&n==5)
         return true;
         lastmove = 2;
         winnable(maze, m+1, n);
    }
    if (n>-1&& maze[m][n-1]!=1 && lastmove!=1){

        if(m==5&&n==5)
         return true;
         lastmove = 3;
         winnable(maze, m, n-1);
    }
    if (m>-1&&maze[m-1][n]!=1 && lastmove!=2){

        if(m==5&&n==5)
         return true;
         lastmove = 4;
        winnable( maze, m-1, n);
    }
      if (m==0&&n==0)
         return false;
       maze[m][n] =1;
       lastmove = lastmove + 2 % 4;
        winnable(maze,m,n);



}

int main() {
   int maze1[5][5] = {{0, 0, 0, 1, 1},
                      {1, 1, 0, 1, 1},
                      {0, 0, 0, 1, 1},
                      {0, 1, 1, 1, 1},
                      {0, 0, 0, 0, 0}};

   int maze2[5][5] = {{0, 0, 0, 0, 1},
                      {0, 1, 0, 1, 1},
                      {0, 1, 1, 0, 0},
                      {0, 0, 0, 1, 0},
                      {1, 0, 1, 0, 0}};

   int maze3[5][5] = {{0, 0, 0, 0, 1},
                      {0, 1, 1, 0, 1},
                      {0, 1, 1, 0, 1},
                      {0, 0, 1, 1, 1},
                      {1, 0, 0, 0, 0}};

   int maze4[5][5] = {{0, 1, 0, 0, 0},
                      {0, 1, 0, 1, 0},
                      {0, 0, 1, 0, 0},
                      {0, 1, 0, 1, 0},
                      {0, 0, 0, 1, 0}};

   cout << boolalpha; // to print bool values as true/false instead of 1/0
   cout << winnable(maze1, 0, 0) << endl;
   cout << winnable(maze2, 0, 0) << endl;
   cout << winnable(maze3, 0, 0) << endl;
   cout << winnable(maze4, 0, 0) << endl;
}