ok,已经解决
1.有好几处小问题,迷宫起点和终点x,y坐标都要-1,从零开始
2.new_x=x1而不是y1
3.判断是否到终点应该拿到外面去
4.起点初始值应该在dfs之前设为1,表示已经走过
5.走过后要恢复案发现场,要回溯
```java
package 蓝桥.递归;
import java.util.*;
/*
输入
2 2 1 ------> 2*2的迷宫 有1个障碍
1 1 2 2 ------>起点坐标(1,1) 终点坐标(2,2)
1 2 ------>(障碍物坐标)
问:从起点到终点有多少种方法
*/
public class 迷宫 {
static Scanner sc=new Scanner(System.in);
static int n=sc.nextInt(),m=sc.nextInt(),t=sc.nextInt(),x0,y0,x1,y1; //n长 m宽
static int[][] data=new int[m][n];//障碍物设为2 做过设成1 没走过为0
static int res=0;
public static void main(String[] args) {
x0=sc.nextInt();
y0=sc.nextInt();
x1=sc.nextInt();
y1=sc.nextInt();
for(int i=0;i<t;i++){
int a=sc.nextInt();
int b=sc.nextInt();
data[a-1][b-1]=2; //障碍物设为2
}
data[x0-1][y0-1]=1;
dfs(x0-1,y0-1);
System.out.println(res);
}
static void dfs(int x,int y){
if(x==x1-1 && y==y1-1){
res++;
return;
}
int[] a={1,-1,0,0}; //四个方向
int[] b={0,0,1,-1};
for(int i=0;i<4;i++){
int new_x=x+a[i],new_y=y+b[i];
if(new_x<0 || new_x>=m || new_y<0 || new_y>=n){ //不能越界
continue;
}
if(data[new_x][new_y]==2){ //有障碍物,不走
continue;
}
if(data[new_x][new_y]==1){ //不重复走
continue;
}
data[new_x][new_y]=1;//走过设为1
dfs(new_x,new_y);
data[new_x][new_y]=0;
}
}
}
```
by huitaiyang @ 2024-01-28 15:33:08