173. 矩阵距离 acwing -多路BFS

原题链接：173. 矩阵距离 - AcWing题库

给定一个 N行 M 列的 01矩阵 A，A[i][j] 与 A[k][l]]之间的曼哈顿距离定义为：

dist(i,j,k,l)=|i−k|+|j−l||

输出一个 N 行 M 列的整数矩阵 B，其中：

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(i,j,x,y)

输入格式

第一行两个整数 N,M

接下来一个 N 行 M 列的 01 矩阵，数字之间没有空格。

输出格式

一个 NN 行 MM 列的矩阵 B，相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤1000

输入样例：

3 4
0001
0011
0110

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

#include<iostream>
#include<algorithm>
#include<cstring>// 定义宏，方便使用pair的first和second成员
#define x first
#define y secondusing namespace std;// 定义一个pair<int, int>类型的别名PII
typedef pair<int,int> PII;// 定义常量N和M，N表示网格的最大行数，M表示队列的最大大小
const int N = 1010, M = N*N;// 定义全局变量n和m，分别表示网格的行数和列数
int n, m;// 定义一个二维字符数组g，用于存储网格中的字符
char g[N][N];// 定义一个队列q，用于广度优先搜索
PII q[M];// 定义一个二维整数数组dist，用于存储每个位置到最近的'1'的距离
int dist[N][N];// 定义广度优先搜索函数bfs
void bfs()
{// 初始化dist数组，所有位置的距离设为-1memset(dist, -1, sizeof dist);// 定义队列的头指针hh和尾指针ttint hh = 0, tt = -1;// 遍历整个网格，将所有值为'1'的位置加入队列，并将它们的距离设为0for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (g[i][j] == '1'){dist[i][j] = 0;q[++tt] = {i, j};}}}// 定义四个方向的移动数组dx和dyint dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// 开始广度优先搜索while (hh <= tt){// 取出队列头部元素auto 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) continue;// 如果新位置已经访问过，则跳过if (dist[a][b] != -1) continue;// 更新新位置的距离，并将其加入队列dist[a][b] = dist[t.x][t.y] + 1;q[++tt] = {a, b};}}
}// 主函数
int main()
{// 读取网格的行数和列数scanf("%d %d", &n, &m);// 读取网格中的字符for (int i = 0; i < n; i++){scanf("%s", g[i]);}// 调用广度优先搜索函数bfs();// 输出每个位置到最近的'1'的距离for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){printf("%d ", dist[i][j]);}printf("\n");}return 0;
}