#include <stdio.h>
#include <iostream>
#define n 4
using namespace std;

bool mazeUtil(int maze[n][n], int x, int y, int sol[n][n]);
bool isValid(int maze[n][n], int x, int y);
bool mazeWorks(int maze[n][n]);

void printSol(int sol[n][n])
{
    for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cout << sol[i][j] + "\n";
        }
    }
}


bool isValid(int maze[n][n], int x, int y)
{
    if(x >= 0 && x < n && y >= 0 && y < n && maze[n][n] == 1)
    {
        return true;
    }
    else{
        return false;
    }
}

bool mazeWorks(int maze[n][n])
{
    int sol[n][n]={{0,0,0,0},
        {0,0,0,0},
        {0,0,0,0},
        {0,0,0,0}};
    };
    if(mazeUtil(maze, 0, 0, sol) == false)
    {
        cout << "no solution";
        return false;
    }
    printSol(sol);
    return true;
}

bool mazeUtil(int maze[n][n], int x, int y, int sol[n][n])
{
    if (x== n-1 && y == n-1)
    {
        sol[x][y]=1;
        return true;
    }
    if(isValid(maze, x, y) == true)
    {
        sol[x][y]=1;
        if(mazeUtil(maze, x+1, y, sol)== true)
        {
            return true;
        }
        if(mazeUtil(maze, x, y+1, sol) == true)
        {
            return true;
        }
        else
        {
            sol[x][y]=0;
            return false;
        }
    }
    return false;
    }
}

int main()
{
    int maze[n][n] ={ { 1,0,0,0},
    {1,1,0,1},
    {0,1,0,0},
    {1,1,1,1}
    };
    mazeWorks(maze);
    return 0;

}