java - 计算矩阵中元素之间的路径数

Question

我正在编写一个代码来计算 n 阶方阵中从 (0,0) 到 (n-1,n-1) 的可用路径数。我尝试使用递归实现代码，但代码给出了 stackoverflow 错误。有人可以帮我找出代码中需要的更正吗？输入在第一行包含测试用例的数量。对于每个测试用例都遵循矩阵顺序的线然后 n x n 矩阵如代码下面的示例输入所示矩阵中1代表一个 block ，只能通过0来追踪路径。

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);
        }
    }

    }

}


}

示例输入:

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

Answer 1

没有什么可以阻止您返回到已经访问过的单元格。