Tom & Jerry

Tom and Jerry are wonderful characters. They are always running and make us laugh.
Right now, they are in a grid of houses and Jerry is running away from Tom. The grid of houses is represented as 0 and 1, where 0 means that Jerry can enter the house, and 1 means Jerry can't. Jerry can only move horizontally or vertically. Also, Jerry doesn't enter the same house more than once.
Jerry started running from the house at (1,1) which is the top-left house in the grid and have to reach (N,N) which the bottom-right house in the grid. You have find the number of ways in which Jerry can reach the destination house where he can be safe.
Input Format
First line is an integer N ( N <= 100), which is the size of the grid. N lines follow, each containing N space separated numbers which are either '0' or '1'.
Output format
Print a single line showing the number of ways in which Jerry can reach from (1,1) to (N,N).

---

Sample Input

9
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0

Sample Output

8512

---

Time Limit: 1 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

import java.io.*;
import java.util.*;
class TestClass
{
    int visit[][],count=0;
    void solve(int arr[][],int x,int y,int end)
    {
        if(x==end-1 && y==end-1) {count++; return;}
        if(x+1<end && arr[x][y]==0 && visit[x][y]!=1) {
            visit[x][y]=1;
            solve(arr,x+1,y,end);
            visit[x][y]=0;
        }
        if(y+1<end && arr[x][y]==0 && visit[x][y]!=1) {
            visit[x][y]=1;
            solve(arr,x,y+1,end);
            visit[x][y]=0;
        }
        if(x-1>=0 && arr[x][y]==0 && visit[x][y]!=1) {
            visit[x][y]=1;
            solve(arr,x-1,y,end);
            visit[x][y]=0;
        }
        if(y-1>=0 && arr[x][y]==0 && visit[x][y]!=1) {
            visit[x][y]=1;
            solve(arr,x,y-1,end);
            visit[x][y]=0;
        }
    }
    public static void main(String args[] ) throws Exception
    {
        TestClass t = new TestClass();
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[][] = new int[N][N];
        for(int i=0;i<N;i++) {
            String str[] = br.readLine().split(" ");
            for(int j=0;j<N;j++) arr[i][j] = Integer.parseInt(str[j]);
        }
        t.visit = new int[N][N];
        t.solve(arr,0,0,N);
        System.out.println(t.count);
        }
}
 

 

Solution 2: 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

class TOMnJerry {
    static int count;
    static int[][] arr;
    static int[][] marked;
    static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];
        marked = new int[n + 1][n + 1];
        String[] str;
        for (int i = 1; i <= n; i++) {
            str = br.readLine().split(" ");
            for (int k = 1; k <= n; k++) {
                arr[i][k] = Integer.parseInt(str[k - 1]);
            }
        }
        if(arr[n][n]==1||(arr[n-1][n]==1&&arr[n][n-1]==1))
           {
               System.out.println("0");
               return;
           }
        recurse(1, 1);
        System.out.println(count);
    }

    static void recurse(int x, int y) {
        if (x == n && y == n) {
            count++;
            return;
        }
        if (x + 1 <= n) {
            if (arr[x + 1][y] != 1 && marked[x + 1][y] != 1) {
                //System.out.println(x + 1 + " " + y + " " + x + " " + y);
                marked[x][y] = 1;
                recurse(x + 1, y);
                marked[x][y] = 0;
            }
        }
        if (y + 1 <= n) {
            if (arr[x][y + 1] != 1 && marked[x][y + 1] != 1) {
                //System.out.println(x + " " + (y + 1) + " " + x + " " + y);
                marked[x][y] = 1;
                recurse(x, y + 1);
                marked[x][y] = 0;
            }
        }
        if (x - 1 > 0) {
            if (arr[x - 1][y] != 1 && marked[x - 1][y] != 1) {
                //System.out.println(x - 1 + " " + y + " " + x + " " + y);
                marked[x][y] = 1;
                recurse(x - 1, y);
                marked[x][y] = 0;
            }
        }
        if (y - 1 > 0) {
            if (arr[x][y - 1] != 1 && marked[x][y - 1] != 1) {
                //System.out.println(x + " " + (y - 1) + " " + x + " " + y);
                marked[x][y] = 1;
                recurse(x, y - 1);
                marked[x][y] = 0;
            }
        }
    }
}