2026-08-02：多源图像渲染。用go语言，给定一个大小为 n 行 m 列的网格，开始时只有部分格子有颜色，这些初始有色格子的位置和颜色由数组 sources 给出，每个元素为 [行, 列, 颜色

2026-08-02：多源图像渲染。用go语言，给定一个大小为 n 行 m 列的网格，开始时只有部分格子有颜色，这些初始有色格子的位置和颜色由数组 sources 给出，每个元素为 [行, 列, 颜色值]；其余格子均为无色，记作 0。

在每个单位时间内，所有已经上色的格子会同时尝试把自己的颜色向上下左右四个相邻的格子传播，但只能传播到当前还没有颜色的格子。如果某个无色格子在同一时间步内被多个不同颜色的来源同时扩散到，那么它会接受其中颜色值最大的那个作为自己的颜色。

这一扩散过程不断重复，直到网格中不再有任何无色格子能被上色为止。最终需要返回整个网格的最终颜色状态。

1 <= n, m <= 100000。

1 <= n * m <= 100000。

1 <= sources.length <= n * m。

sources[i] = [ri, ci, colori]。

0 <= ri <= n – 1。

0 <= ci <= m – 1。

1 <= colori <= 1000000​。

sources 中的所有 (ri, ci​​​​​​​) 互不相同。

输入： n = 3, m = 3, sources = [[0,0,1],[2,2,2]]。

输出： [[1,1,2],[1,2,2],[2,2,2]]。

解释：

每个时间步的网格如下：

在时间步 2，单元格 (0, 2)，(1, 1) 和 (2, 0) 同时被两种颜色到达，因此它们被分配颜色 2，因为它是其中的最大值。

题目来自力扣3905。

详细步骤

第一步：获取输入并初始化结果网格

• 给定网格的行数 n、列数 m 以及所有初始着色点 sources。
• 创建一个 n × m 的二维整数数组 ans，所有元素初始为 0，表示未着色。

第二步：对初始源点按颜色值降序排序

• 将 sources 数组按每个元素的第三个值（颜色值）从大到小排序。
• 排序后，颜色值大的源点排在前面，这样后续处理时会优先扩展。

第三步：填充初始颜色并构建队列

• 遍历排序后的 sources，对于每个 [r, c, color]：
  • 将 ans[r][c] 设为 color（即放置初始颜色）。
  • 同时将该三元组 [r, c, color] 加入一个队列 q 中（队列初始就是排序后的 sources 列表）。

第四步：广度优先扩散（核心循环）

• 当队列 q 不为空时，重复以下操作：
• 从队首取出一个元素 [x, y, c]，它表示坐标 (x, y) 当前颜色为 c，并且该格子已经着色，准备向四周扩散。
• 检查四个相邻方向（左、右、上、下），即 (x, y-1)、(x, y+1)、(x-1, y)、(x+1, y)。
• 对于每个邻居坐标 (i, j)：
  • 首先判断 (i, j) 是否在网格范围内（0 ≤ i < n 且 0 ≤ j < m）。
  • 如果该邻居当前在 ans 中的值为 0（表示尚未着色），则：
    • 将其颜色赋值为当前颜色 c，即 ans[i][j] = c。
    • 将新的三元组 [i, j, c] 追加到队列尾部，以便以后继续从该格子向外扩散。
  • 如果邻居已经非零（已有颜色），则忽略（不覆盖）。

第五步：循环结束，返回结果

• 当队列为空时，说明所有能被着色的格子都已经扩散到，此时 ans 矩阵即为最终网格状态。

为什么排序 + BFS 能正确模拟“同时到达取最大”

• 所有源点都在时刻 0 同时开始扩散，但我们的 BFS 是串行处理的。
• 由于先处理高颜色值的源点，当它扩展到某个相邻格子时，会立刻占据它（如果该格尚未被占据）。
• 同一时刻，低颜色值的源点也在尝试扩展相同的格子，但因为该格子已经被高颜色占据（非零），低颜色源在后续处理时就会跳过它，从而不会覆盖。
• 对于距离较远的格子，高颜色源需要更多步才能到达，而低颜色源如果距离更近，会先到达并占据，高颜色源之后到达时发现非零，也不会覆盖。这恰好符合“先到先得”的原则，而“同时到达”的情况实际上就是处理顺序决定的：同一时间步内先处理高色源，后处理低色源，高色优先占据，因此等效于取最大值。

因此，该算法正确模拟了题目要求的扩散规则。

复杂度分析

• 时间复杂度

  • 排序初始源点：O(K log K)，其中 K = sources.length，且 K ≤ n * m。
  • BFS 遍历每个格子最多一次，因为每个格子一旦着色就不再改变，所以总扩展次数为 O(n * m)。
  • 总体时间复杂度为 O(K log K + n * m)。由于 K ≤ n * m，最坏情况下可表示为 O(N log N)，其中 N = n * m。

• 额外空间复杂度

  • 结果网格 ans 占用 O(n * m)。
  • 队列 q 最多存储所有已着色的格子（包括初始源点和扩散过程中新着色的），数量不超过 n * m，因此也占用 O(n * m)。
  • 排序使用的额外空间通常为递归栈 O(log K)（可忽略）或原地排序无额外大空间。
  • 因此总额外空间复杂度为 O(n * m)。

最终，算法返回的 ans 矩阵即为题目所求的最终网格着色结果。

Go完整代码如下：

package main

import (
"fmt"
"slices"
)

var dirs = []struct{ x, y int }{{0, –1}, {0, 1}, {–1, 0}, {1, 0}} // 左右上下

func colorGrid(n, m int, sources [][]int) [][]int {
slices.SortFunc(sources, func(a, b []int) int { return b[2] – a[2] })

ans := make([][]int, n)
for i := range ans {
ans[i] = make([]int, m)
}
for _, p := range sources {
ans[p[0]][p[1]] = p[2] // 初始颜色
}

q := sources
for len(q) > 0 {
p := q[0]
q = q[1:]
x, y, c := p[0], p[1], p[2]
for _, d := range dirs { // 向四个方向扩散
i, j := x+d.x, y+d.y
if 0 <= i && i < n && 0 <= j && j < m && ans[i][j] == 0 { // (i, j) 未着色
ans[i][j] = c // 着色
q = append(q, []int{i, j, c}) // 继续扩散
}
}
}

return ans
}
func main() {
n := 3
m := 3
sources := [][]int{{0, 0, 1}, {2, 2, 2}}
result := colorGrid(n, m, sources)
fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from collections import deque
from typing import List

def colorGrid(n: int, m: int, sources: List[List[int]]) –> List[List[int]]:
# 按颜色从大到小排序（高优先级先扩散）
sources_sorted = sorted(sources, key=lambda x: x[2], reverse=True)

# 初始化网格，全部填 0
ans = [[0] * m for _ in range(n)]

# 放置初始颜色
q = deque()
for r, c, color in sources_sorted:
ans[r][c] = color
q.append((r, c, color)) # 队列中存储坐标和颜色

# 四个方向：左、右、上、下
dirs = [(0, –1), (0, 1), (–1, 0), (1, 0)]

while q:
x, y, col = q.popleft()
for dx, dy in dirs:
i, j = x + dx, y + dy
# 检查边界且未着色
if 0 <= i < n and 0 <= j < m and ans[i][j] == 0:
ans[i][j] = col
q.append((i, j, col))

return ans

# 测试用例
if __name__ == "__main__":
n = 3
m = 3
sources = [[0, 0, 1], [2, 2, 2]]
result = colorGrid(n, m, sources)
for row in result:
print(row)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

// 四个方向：左、右、上、下
const array<pair<int, int>, 4> dirs = {{{0, –1}, {0, 1}, {–1, 0}, {1, 0}}};

vector<vector<int>> colorGrid(int n, int m, vector<vector<int>>& sources) {
// 按颜色值降序排序（高优先级先处理）
sort(sources.begin(), sources.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] > b[2];
});

// 初始化网格
vector<vector<int>> ans(n, vector<int>(m, 0));

// 填充初始颜色，同时构建队列（直接使用 sources 作为队列容器）
vector<vector<int>> q;
q.reserve(sources.size()); // 预分配空间
for (auto& p : sources) {
int r = p[0], c = p[1], color = p[2];
ans[r][c] = color;
q.push_back({r, c, color});
}

// BFS 扩散（使用 head 指针模拟队列）
size_t head = 0;
while (head < q.size()) {
auto& cur = q[head++];
int x = cur[0], y = cur[1], col = cur[2];
for (auto [dx, dy] : dirs) {
int i = x + dx, j = y + dy;
if (i >= 0 && i < n && j >= 0 && j < m && ans[i][j] == 0) {
ans[i][j] = col;
q.push_back({i, j, col});
}
}
}

return ans;
}

int main() {
int n = 3, m = 3;
vector<vector<int>> sources = {{0, 0, 1}, {2, 2, 2}};
auto result = colorGrid(n, m, sources);

// 输出结果
for (const auto& row : result) {
for (int val : row) {
cout << val << " ";
}
cout << endl;
}
return 0;
}