sách gpt4 ai đã đi

Thuật toán - Màu sắc được bao quanh bởi một màu khác trong một ma trận

In lại 作者:行者123 更新时间:2023-12-02 02:40:10 28 4
mua khóa gpt4 Nike

我最近在一次采访中遇到了这个问题:

给出以下矩阵:

[[ R R R R R R],
[ R B B B R R],
[ B R R R B B],
[ R B R R R R]]

找出是否有任何一组只有 R 或只有 B 被 4 个方向上的相反颜色包围:上、下、左、右角。

例如:上述矩阵的答案 -> 在第二行中被 R 包围的有效 B 集。
[[ R R R R R R],
[ R **B B B** R R],
[ B R R R B B],
[ R B R R R R]]

我尝试对所有方向的特定颜色进行 BFS,但无法找到解决方案。
有人可以指导我解决问题。

1 Câu trả lời

要找到被 R 细胞包围的 B 细胞组,请将矩阵视为一个图,其顶点都是 B 细胞,边连接相邻的 B 细胞。使用 BFS(或 DFS)查找 connected components的,但忽略包含边界上的单元格的连接组件。每个(非边界)连接组件包含一组由 R 单元格包围的 B 单元格。然后,为了找到被 B 细胞包围的 R 细胞组,类似地计算顶点是 R 细胞的图的非边界连通分量。

由于两个图的顶点数和边数都是O(mn)并且可以在与图的大小成线性关系的时间内找到图的连通分量集,该算法的运行时间为O(mn) .

关于算法 - 矩阵中被另一种颜色包围的颜色,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60036756/

28 4 0
行者123
Hồ sơ cá nhân

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá Didi Taxi miễn phí
Mã giảm giá Didi Taxi
Giấy chứng nhận ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com