Robot moving in a grid

Question

A robot is located at the top-left corner of a 4x4 grid. The robot can move either up, down, left, or right, but can not visit the same spot twice. The robot is trying to reach the bottom-right corner of the grid.The number of ways it can reach the bottom-right corner of the grid is?

Now i know that if the robot can only move down or right ,then the answer would be 8C4 because it has to go 4 squares to the right and 4 squares down, in any order.

But i am having difficulty in solving the problem when the robot can move both left and up!?

I just need a hint to solve the problem! How should i approach the problem?

Answer 1

This will work fine. The answer is 184.

public class RobotMovementProblem 
{
    public static void main(String[] args) 
    {
        int grid[][]=new int[4][4];
        System.out.println(countPaths(grid, 0, 0));
    }
    static int countPaths(int grid[][],int i,int j)
    {

        if ( i < 0 || j < 0 || i >= 4 || j >= 4 ) return 0;
        if ( grid[i][j] == 1 ) return 0;
        if ( i == 3 && j == 3 ) return 1;
        int arr[][]=new int[4][4];
        for(int m=0;m<4;m++)
        {
            for(int n=0;n<4;n++)
            {
                arr[m][n]=grid[m][n];
            }
        }

        arr[i][j] = 1;
        return countPaths(arr, i, j+1) + countPaths(arr, i, j-1) +  countPaths(arr, i+1, j) + countPaths(arr, i-1, j);  
    }
}