\color{Red}{矩阵距离——多源BFS最短路}
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
给定一个 N 行 M 列的 01 矩阵 A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:
dist(A[i][j],A[k][l])=|i−k|+|j−l|输出一个 N 行 M 列的整数矩阵 B,其中:
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
输入格式
第一行两个整数 N,M。
接下来一个 N 行 M 列的 01 矩阵,数字之间没有空格。
输出格式
一个 N 行 M 列的矩阵 B,相邻两个整数之间用一个空格隔开。
数据范围
1 ≤ N, M ≤ 1000
输入样例:
3 4
0001
0011
0110
输出样例:
3 2 1 0
2 1 0 0
1 0 0 1
思路
多源BFS的基础就是 Dijkstra 算法,其思想是:如果在一个没有负权边的图,我们每次找寻距离源点最近的点,并更新这个点的邻接点,找寻局部最优,遍历全部节点,可以达到全局最优。
而多源BFS即我们把最开始全部的起点放入队列。
为什么可以这么做?
多源BFS的依据是,放入的这些点都相当于起点,而我们可以想象出逻辑存在一个单源节点,这个节点距离这些起点集合的节点距离都为0,我们依次遍历,即变成Dijkstra算法。
import java.io.*;
import java.util.Arrays;
public class Main {
static int N = 1010, n, m, hh, tt = -1;
static int[][] d = new int[N][N];
static PII[] q = new PII[N * N];
static int[][] g = new int[N][N];
static class PII {
int x, y;
public PII() {
}
public PII(int x, int y) {
this.x = x;
this.y = y;
}
}
static void bfs() throws IOException {
int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
while (hh <= tt) {
PII t = q[hh++];
for (int i = 0; i < 4; i++) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m || d[a][b] != -1) continue;
q[++tt] = new PII(a, b);
d[a][b] = d[t.x][t.y] + 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) bw.write(d[i][j] + " ");
bw.newLine();
}
bw.flush();
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for (int i = 0; i < n; i++) {
Arrays.fill(d[i], -1);
String[] s2 = br.readLine().split("");
for (int j = 0; j < m; j++) {
g[i][j] = Integer.parseInt(s2[j]);
if (g[i][j] == 1) {
q[++tt] = new PII(i, j);
d[i][j] = 0;
}
}
}
bfs();
}
}