//Problem Statement : A robot is located in the upper-left corner of a 4×4 grid.

//The robot can move either up, down, left, or right, but cannot go to the same location twice.

//The robot is trying to reach the lower-right corner of the grid. Your task is to find out

//the number of unique ways to reach the destination.

//INPUT SAMPLE:

//There is no input for this program.

//OUTPUT SAMPLE:

//Print out the number of unique ways for the robot to reach its destination.

//The number should be printed out as an integer ≥0.

package com.practice;

public class BotMovement

{

final int N = 4;

void printSolution(int sol[][])

{

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

System.out.print(" " + sol[i][j] +

" ");

System.out.println();

}

}

boolean isSafe(int grid[][], int x, int y)

{

// if (x,y outside grid) return false

return (x >= 0 && x < N && y >= 0 &&

y < N && grid[x][y] == 1);

}

boolean solvegrid(int grid[][])

{

int sol[][] = {{0, 0, 0, 0},

{0, 0, 0, 0},

{0, 0, 0, 0},

{0, 0, 0, 0}

};

if (solvegridUtil(grid, 0, 0, sol) == false)

{

System.out.print("Solution doesn't exist");

return false;

}

printSolution(sol);

return true;

}

boolean solvegridUtil(int grid[][], int x, int y,

int sol[][])

{

// if (x,y is goal) return true

if (x == N - 1 && y == N - 1)

{

sol[x][y] = 1;

return true;

}

// Check if grid[x][y] is valid

if (isSafe(grid, x, y) == true)

{

// mark x,y as part of solution path

sol[x][y] = 1;

if (solvegridUtil(grid, x + 1, y, sol))

return true;

if (solvegridUtil(grid, x, y + 1, sol))

return true;

if (solvegridUtil(grid, x - 1, y, sol))

return true;

if (solvegridUtil(grid, x, y - 1, sol))

return true;

sol[x][y] = 0; // backtrack

return false;

}

return false;

}

public static void main(String args[])

{

BotMovement bot = new BotMovement();

int grid[][] = {{1, 0, 0, 0},

{1, 1, 0, 1},

{0, 1, 0, 0},

{1, 1, 1, 1}

};

bot.solvegrid(grid);

}

}