题目描述
blablabla
样例
blablabla
算法2
Java 代码
import java.util.*;
public class Main {
static class Node {
int x;
int y;
int val;
public Node(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
}
static int[][] dist;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int m = s.nextInt();
int n = s.nextInt();
int[][] a = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = s.nextInt();
}
}
dist = new int[m][n]; // 从起点到各个点的最短距离
// 权值都相同的最短路使用bfs。将二维数据放到队列中
LinkedList<Node> q = new LinkedList<>();
q.offer(new Node(0, 0, 1));
while (!q.isEmpty()) {
Node tmp = q.poll();
for (int i = 0; i < 4; i++) {
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && a[nx][ny] == 0) {
if (dist[nx][ny] == 0) {
dist[nx][ny] = dist[tmp.x][tmp.y] + 1;
q.offer(new Node(nx, ny, 1));
if (nx == m - 1 && ny == n - 1) {
System.out.print(dist[nx][ny]);
return;
}
}
}
}
}
}
}