//rat in a maze
#include <stdio.h>
#include <stdlib.h>
#define N 6

void printMaze(int maze[N][N]){
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      printf("%3d", maze[i][j]);
    }
    printf("\n");
  }
  printf("\n");
}

int isSafe(int maze[N][N], int x, int y){
  return (x>=0 && x < N && y>=0 && y < N && maze[x][y]==1);
}

int mazeSolver(int maze[N][N], int x, int y){
  if(x==N-1 && y==N-1){
    maze[x][y]=2;
    return 1;
  }

  if(isSafe(maze, x, y)){
    maze[x][y]=2;

    if(mazeSolver(maze, x+1, y)){
      return 1;
    }

    if(mazeSolver(maze, x, y+1)){
      return 1;
    }
    maze[x][y]=0;
    return 0;

  }
  return 0;
}

void mazeSolve(){
  int maze[N][N] = {
    {1, 1, 1, 1, 0, 0},
    {0, 0, 1, 0, 0, 0},
    {1, 1, 1, 1, 1, 1},
    {1, 0, 0, 1, 0, 0},
    {1, 1, 1, 1, 1, 1},
    {0, 0, 0, 0, 0, 1}
  };
  if(mazeSolver(maze, 0, 0)==0){
    printf("No solution\n");
    return;
  }else{
    printMaze(maze);
  }
  return;
}

int main(){
  mazeSolve();
}