如何构建连接组件的图形？

Question

假设我有一个字符矩阵（A，B，...）。我想查找所有填充相同字符的连续“区域”，并创建一个顶点对应于这些“区域”的图形。当且仅当对应区域具有共同的边界时，图顶点才被连接。

例如：

 
input matrix: 
A A B C 
A B B B 
C C D D 

areas: 
1(A), 2(B), 3(C), 4(C), 5(D) 

output graph (adjacency list): 

1(A) - 2(B), 4(C) 
2(B) - 1(A), 3(C), 4(C), 5(D) 
3(C) - 2(B) 
4(C) - 1(A), 2(B), 5(D) 
5(D) - 2(B), 4(C)

我的问题是：如何建立给定的矩阵这样的曲线图。

显然，我可以这样做：

• 运行BFS/DFS找到连接组件（“区”）
• 扫描矩阵再次找到邻居每个“区”。

有没有更简单和更有效的方法来做到这一点？

Answer 1

我不认为有更好的解决方案。
一些优化可能会将字符转换为int。 但是这不会改变大O符号的努力。

有些人可能想要在比特字段中存储信息来赢得速度竞赛， 但这不值得付出努力，代码也不会被读取。