#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;
const int M=5;

int mtrx[M][M]= {1, 1, 1, 0, 0,
                 1, 1, 1, 1, 1,
                 0, 1, 1, 1, 0,
                 1, 1, 1, 0, 0,
                 0, 0, 1, 1, 1,
                };

int overflow=M*M;
int legjobb = overflow;
int legjobbmtrx[M][M];
void backtrack(int x, int y, int steps, int aktualismtrx[][M])
{

    if(x<0 || x>M-1 || y<0 || y>M-1) return;
    if(steps>overflow || steps > legjobb) return;
    steps++;
    aktualismtrx[x][y] = 1;
    if(x == M-1 || y == M-1){
        if(steps < legjobb){
            legjobb = steps;
            for(int i = 0; i < M; ++i){
                for(int j = 0; j < M; ++j){
                    legjobbmtrx[i][j] = aktualismtrx[i][j];
                }
            }
        }
    }

    if(steps>overflow || steps > legjobb) return;

    if(mtrx[x+1][y] == 1) backtrack(x+1, y, steps, aktualismtrx);
    if(mtrx[x][y+1] == 1) backtrack(x, y+1, steps, aktualismtrx);
    if(mtrx[x-1][y] == 1) backtrack(x-1, y, steps, aktualismtrx);
    if(mtrx[x][y-1] == 1) backtrack(x, y-1, steps, aktualismtrx);
}

int main()
{
    int aktualismtrx [M][M];

    for(int i = 0; i < M; ++i)
    {
        for(int k = 0; k < M; ++k)
            for(int j = 0; j < M; ++j)
                aktualismtrx[k][j] = 0;
        if(mtrx[i][0] == 1)
        {
            backtrack(i,0,0,aktualismtrx);
        }
        for(int k = 0; k < M; ++k)
            for(int j = 0; j < M; ++j)
                aktualismtrx[k][j] = 0;
        if(mtrx[0][i] == 1)
        {
            backtrack(0,i,0,aktualismtrx);
        }

    }

    for(int i = 0; i < M; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            cout<<legjobbmtrx[i][j]<<' ';
        }
        cout<<endl;
    }
}