矩阵距离

BFS 多源BFS

题目

173. 矩阵距离 - AcWing题库 给定一个 $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]=mi{n}_{1\le x\le N,1\le y\le M,A[x][y]=1}dist(A[i][j],A[x][y])$

输入格式

第一行两个整数 $N,M$。

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

输出格式

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

数据范围

$1\le N,M\le 1000$

输入样例：

3 4
0001
0011
0110

输出样例：

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

思路

和正常的BFS求最短路一样, 这里需要把所有为1的点加入初始队列中。

即求每个1能走到的最短路径, 因为队列中的点满足两段性和单调性：

• 两段性： [x,x,x,x,][x+1,x+1,x+1] x为访问到该点的距离
• 单调性：[x,x,x,x,][x+1,x+1,x+1][...x+1] 新加入的点也是x+1 故满足当访问到一个0点时, 当前被哪一个1泛洪覆盖到, 该0点的最短距离就是和1的距离。之后其他1点泛洪过来的距离一定不是最优距离。

故可以通过从1点逆向求最短路得到答案。

代码

#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e3 + 10;
int n,m;
int g[N][N];
int dist[N][N];
PII q[N*N];
int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
 
 
void bfs()
{
    int hh = 0, tt = -1;
    memset(dist, -1, sizeof dist);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(g[i][j])
            {
                q[++tt] = {i,j};
                dist[i][j] = 0;
            }
    while(hh <= tt)
    {
        auto t = q[hh++];
        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 1 || a > n || b < 1 || b > m || dist[a][b] != -1) continue;
            dist[a][b] = dist[x][y] + 1;
            q[++tt] = {a,b};
        }
    }
}
 
int main()
{
    cin >> n >> m;
    cin.get();
    for(int i = 1; i <= n; i++)
    {
        for(int j =1; j <= m; j++)
        {
            char c;
            cin >> c;
            g[i][j] = c - '0';
        }
        cin.get();
    }
    bfs();
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}