解析
经典的bfs问题。四个方向标记,visited[][]数组标记是否走过。用队列实现,其中添加一个元素为steps储存到达该结点的步长。每个队列元素是一个int[]{x,y,step}的数组。
其中要考虑边界情况,找到目标结点就可以退出了,找不到返回-1。每次访问新节点,记得设置标记访问过了。
代码
import java.util.*;
public class Main {
// 定义方向数组,分别表示上、下、左、右四个方向
private static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static int minSteps(int[][] maze) {
int n = maze.length;
int m = maze[0].length;
boolean[][] visited = new boolean[n][m]; //标记已经访问过的点
int startX = 0, startY = 0; // 初始化起点位置
// 初始化 BFS 队列
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startX, startY, 0}); // 记录位置及步数
visited[startX][startY] = true;
// BFS核心算法
while (!queue.isEmpty()) {
int[] currentPosition = queue.poll(); //弹出当前位置坐标和步数
int x = currentPosition[0];
int y = currentPosition[1];
int steps = currentPosition[2];
// 如果到达终点,则返回步数
if (x == n - 1 && y == m - 1) return steps;
for (int[] dir : directions) { // 遍历四个方向
int newX = x + dir[0];
int newY = y + dir[1];
// 判断新位置是否合法且未访问过
if (newX >= 0 && newX < n && newY >= 0 && newY < m && maze[newX][newY] == 0 && !visited[newX][newY]) {
queue.offer(new int[]{newX, newY, steps + 1}); //步数+1,添加,设置为访问过该结点了
visited[newX][newY] = true;
}
}
}
return -1; // 如果无法到达终点,则返回 -1
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int [][]maze=new int[n][m];
for(int i=0;i<maze.length;i++){
for(int j=0;j<maze[0].length;j++){
maze[i][j]=sc.nextInt();
}
}
System.out.println(minSteps(maze));
}
}