矩阵距离

题目描述

给定 $N \times M$ 的 01 矩阵，输出每个格子到最近的 1 的曼哈顿距离（ $1 \le N,M \le 1000$ ）。

思路

所有 1 同时作为源点开始多源 BFS 逐层向四邻扩散，某格子首次被扩散到的层数即为到最近 1 的距离；每格最多入队一次， $O(NM)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27import sys
from collections import deque

def main() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, m = int(next(data)), int(next(data))
    # 矩阵压成一维，格子 i 的行列为 (i // m, i % m)
    # 每行的数字之间没有空格，所以一个 token 就是一行，按行数顺序消费即可
    g = b"".join(next(data) for _ in range(n))  # n 行拼接成一长串，共 n*m 个字符
    dist = [-1] * (n * m)
    q = deque()
    for i in range(n * m):
        if g[i] == 49:  # 字符 '1'：作为多源 BFS 的源点，距离 0
            dist[i] = 0
            q.append(i)
    while q:  # 多源 BFS：所有源点同层扩展，pop 时距离即最近 1 的曼哈顿距离
        u = q.popleft()
        r, c = divmod(u, m)
        d = dist[u] + 1
        for v in (u - m if r else -1, u + m if r < n - 1 else -1, u - 1 if c else -1, u + 1 if c < m - 1 else -1):
            if v >= 0 and dist[v] < 0:
                dist[v] = d
                q.append(v)
    # 按行拼好输出，避免逐格 join
    print("\n".join(" ".join(map(str, dist[i : i + m])) for i in range(0, n * m, m)))

main()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:40
 * update_at: 2026-10-06 11:40
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;          // 行数上限
const int MAXM = 1005;          // 列数上限
const int MAXV = MAXN * MAXM;   // 一维总格子数上限

int n, m;                       // 矩阵行列
char g[MAXN][MAXM];             // 输入的 01 矩阵
int dist[MAXV];                 // 一维下标到最近 1 的曼哈顿距离，-1 表示未访问
int q[MAXV];                    // 手写队列

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%s", g[i]);

    int total = n * m;
    for (int i = 0; i < total; ++i) dist[i] = -1;

    int head = 0, tail = 0;
    // 把所有 1 作为多源 BFS 的源点，距离为 0，一起入队
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == '1') {
                int u = i * m + j;
                dist[u] = 0;
                q[tail++] = u;
            }
        }
    }

    // 多源 BFS：每轮扩展一层，第一次到达某格时的层数即最近距离
    while (head < tail) {
        int u = q[head++];
        int r = u / m;          // 行号
        int c = u % m;          // 列号
        int d = dist[u] + 1;    // 邻居距离
        // 上
        if (r > 0) {
            int v = u - m;
            if (dist[v] < 0) {
                dist[v] = d;
                q[tail++] = v;
            }
        }
        // 下
        if (r + 1 < n) {
            int v = u + m;
            if (dist[v] < 0) {
                dist[v] = d;
                q[tail++] = v;
            }
        }
        // 左
        if (c > 0) {
            int v = u - 1;
            if (dist[v] < 0) {
                dist[v] = d;
                q[tail++] = v;
            }
        }
        // 右
        if (c + 1 < m) {
            int v = u + 1;
            if (dist[v] < 0) {
                dist[v] = d;
                q[tail++] = v;
            }
        }
    }

    // 按原矩阵形状输出距离
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (j) putchar(' ');
            printf("%d", dist[i * m + j]);
        }
        putchar('\n');
    }
    return 0;
}

目录

题目描述

思路

参考代码