CODEWITHSUNDEEP
javarecursion
Shamik Ur Rahman Khan
Shamik Ur Rahman Khan

Reputation: 25

counting number of paths between elements in a matrix

I am writing a code to count the number of paths available from (0,0) to (n-1,n-1) in a square matrix of order n. I have tried to implement a code using recursion but the code gives stackoverflow error. Can someone help me findout the correction needed in my code. input contains number of test cases in first line. for each test case follows a line with order of matrix then n x n matrix follows as shown in sample input below the code In a matrix 1 represents a block, a path can be traced only through 0s.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.lang.Integer;
import java.util.LinkedList;
import java.lang.Math.*;



public class TestClass {

public static int ans,arr[][];



public static void main(String args[] )throws Exception{
    File file=new File("C:\\Users\\Mujeeb\\Desktop\\ii.txt");
    BufferedReader br = new BufferedReader(new InputStreamReader(new 
                        FileInputStream(file), "ASCII"));
    int cases = Integer.valueOf(br.readLine());

    for(int x=0; x<cases;x++){
        int n= Integer.valueOf(br.readLine());
        ans=0;
        arr=new int[n][n];
        for(int t1=0;t1<n;t1++){
            int t2=0;
            for(String s:br.readLine().split("\\s+")){
                arr[t1][t2]=Integer.valueOf(s);
                t2++;
            }

        }
        if(arr[0][0]==1 || arr[n-1][n-1]==1){
            System.out.println(ans);
        }else{
            if(arr[0][1]==0){
                findpath(0,1,0,0,n);
            }
            if(arr[1][0]==0){
                findpath(1,0,0,0,n);
            }
            System.out.println(ans);
        }


    } 
}

public static void findpath(int x,int y,int xp,int yp,int n){

    if(x==n-1 &&y==n-1){
        ans++;
    }
    else{

    if(x<n-1){
        if(arr[x+1][y]==0 && !((x+1==xp) && (y==yp))){

            findpath(x+1,y,x,y,n);
        }
    }

    if(x>0){
        if(arr[x-1][y]==0 && !((x-1==xp) && (y==yp))){

            findpath(x-1,y,x,y,n);
        }
    }

    if(y<n-1){
        if(arr[x][y+1]==0 && !((x==xp) && (y+1==yp))){

            findpath(x,y+1,x,y,n);
        }
    }

    if(y>0){
        if(arr[x][y-1]==0 && !((x==xp) && (y-1==yp))){

            findpath(x,y-1,x,y,n);
        }
    }

    }

}


}

sample input:

1
4
0 1 1 0
0 0 1 0
0 0 0 0
0 1 1 0

Upvotes: 0

Views: 69

Answers (1)

Maurice Perry
Maurice Perry

Reputation: 9658

There is nothing preventing you to go back to a cell you've already visited.

Upvotes: 1

Related Questions