走迷宫JavaDFS
作者:
husheng
,
2024-11-30 17:08:37
,
所有人可见
,
阅读 1
import java.util.Scanner;
public class Main {
static int r,c;
static boolean[][] vis;//标记有没有走过
static char[][] arr;//地图
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int min = Integer.MAX_VALUE;
public static void dfs(int x,int y,int ans) {//xy表示当前坐标,ans表示当前是第几步
if(x==r-1&&y==c-1) {//找到出口
min = Math.min(min, ans);
return ;
}
for(int a=0;a<4;a++) {
int newx = x+dx[a];
int newy = y+dy[a];
if(newx>=0&&newx<r&&newy>=0&&newy<c&&arr[newx][newy]=='.'&&vis[newx][newy]==false) {
vis[newx][newy]=true;//标记为走过
dfs(newx,newy,ans+1);
vis[newx][newy]=false;
}
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
r = input.nextInt();
c = input.nextInt();
arr = new char[r][c];
for(int i=0;i<r;i++) {
arr[i] = input.next().toCharArray();
}
vis=new boolean[r][c];
vis[0][0] = true;//将起始点标记为走过
dfs(0,0,0);
System.out.println(min+1);
}
}