9.8华为机试第二题

//运行超时，dfs
import java.util.*;

public class HuaiWei2_0 {
    private static List<List<int[]>> res;
    private static List<int[]> path;
    private static int step=0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //处理输入
        String[] str = sc.nextLine().split("\\,");
        int m = Integer.parseInt(str[0]);
        int n = Integer.parseInt(str[1]);
        int[][] arr = new int[m][n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                arr[i][j] = sc.nextInt();
            }
        }
        //调用递归
        res = new ArrayList<>();
        path = new ArrayList<>();
        boolean[][] isVisited = new boolean[m][n];
        isVisited[0][0]=true;
        path.add(new int[]{0,0});//加入起点
        dfs(arr, 0, 0, isVisited);
        //找到最小步数
        int min=Integer.MAX_VALUE;
        for(List<int[]> list : res){
            int tmp = list.size();
            if(tmp<min) min = tmp;
        }
        if(res.size()==0) System.out.println(-1);
        else System.out.println(min-1);

        System.out.println(step);
    }

    private static void dfs(int[][] arr, int x, int y, boolean[][] isVisited){
        step++;
        //边界条件
        if(x>=arr.length||x<0||y>=arr[0].length||y<0||arr[x][y]==0) return;
        //终止条件
        if(x==arr.length-1 && y==arr[0].length-1){
            res.add(new ArrayList<>(path));return;
        }

        //选择走下
        for(int i=1; i<=arr[x][y] && i+x<arr.length; i++){
            if(isVisited[x+i][y]) continue;
            isVisited[x+i][y]=true;
            path.add(new int[]{x+i, y});
            dfs(arr, x+i, y, isVisited);
            path.remove(path.size()-1);
            isVisited[x+i][y]=false;
        }

        //选择走右
        for(int i=1; i<=arr[x][y] && i+y<arr[0].length; i++){
            if(isVisited[x][y+i]) continue;
            isVisited[x][y+i]=true;
            path.add(new int[]{x, y+i});
            dfs(arr, x, y+i, isVisited);
            path.remove(path.size()-1);
            isVisited[x][y+i]=false;
        }
    }
}