9.8华为机试第二题
我用dfs做的，超时了，怎么优化啊，代码如下，我尝试用isVisited数组，但dfs次数是一样的，是测试用例问题吗？
有没有大佬用dfs AC出来的？
//运行超时，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;
}
}
} 