2

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

例如：

输入矩阵：
AABC
ABBB
CCDD

领域：
1(A)、2(B)、3(C)、4(C)、5(D)

输出图（邻接表）：

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 以查找连接的组件（“区域”）
  • 再次扫描矩阵以找到每个“区域”的邻居。

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

4

1 回答 1

1

I dont think that there is a much better solution.
Some optimisation would be possible converting characters to int. But this would not change the effort in big O Notation.

Some might want to to store the info in bit fields to win a speed contest, but this is not worth the effort, neither the code would be readable.

于 2012-11-30T20:44:32.983 回答