#include <iostream>
#include <fstream>

using namespace std;

bool rat_walk(bool maze[4][4] , int pos_x , int pos_y , bool track[4][4])
{

    if(pos_x == 3 && pos_y == 3)
    {
        return true;
    }

    if(maze[pos_y][pos_x] == 0)
        return false;

    if(rat_walk(maze,pos_x+1,pos_y,track))
    {
        track[pos_y][pos_x+1] = 1;
    }else if(rat_walk(maze,pos_x,pos_y+1,track))
    {
        track[pos_y+1][pos_x] = 1;
    }
}

int main()
{
    ifstream in("maze.txt");
    bool maze[4][4];
    bool track[4][4] = {0};
    track[0][0] = 1;

    for(int i = 0 ; i < 4 ; i++){
        for(int k = 0 ; k < 4 ; k++){
            in >> maze[i][k];
        }
    }

    if(rat_walk(maze,0,0,track)){
        for(int i = 0 ; i < 4 ; i++){
        for(int k = 0 ; k < 4 ; k++){
            cout << track[i][k] << "  ";
        }
        cout << endl;
    }
    }else{
        cout << "nincs ut";
    }

    return 0;
}