最长路径的个数_美团笔面试算法题解答

这个题目的解决方案我采用的是dfs加上回溯的方法

import java.util.Scanner;

public class Main {
    private static int maxLen = 0;
    private static int[][] steps = {{1,0},{-1,0},{0,1},{0,-1}};
    private static boolean[][] arr;
    private static int num = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        arr = new boolean[m][n];
        sc.close();
        if(m <=0 || n<= 0)
            System.out.println(0);
        else{
            dfs(0,0,1);
            System.out.println(num);
        }
    }

    public static int dfs(int startX, int startY, int currentLen){
        if(startX>=arr.length || startY>=arr[0].length || startY<0 || startX<0)
            return 0;
        if(arr[startX][startY])
            return 0;

        arr[startX][startY] = true;
        if(startX == arr.length - 1 && startY == arr.length -1){ // 走完了
            if(currentLen == maxLen){
                num ++;
            }else if(currentLen > maxLen){
                num = 1;
                maxLen = currentLen;
            }
        }
        for(int[] step:steps){
            int x = startX+step[0];
            int y = startY+step[1];
            int status = dfs(x,y,currentLen+1);
            if(status == 1){
                arr[x][y] = false;
            }
        }
        return 1;
    }
}