我试图用0和1随机填充2d数组。条件是，每个1必须"放置"在另一个1旁边，垂直或水平，但不是对角线。
http://prntscr.com/8nzl19在截图中，你可以看到3块15。我想让它们"连接"起来，这样就只有一个15块了。
有什么算法或什么东西可以做到这一点吗?
由于一种简单的方法是用1填充整个矩阵，所以我假设您需要将0变为1的最小数量。
这里有一个你可以使用的方法:
- 求矩阵中所有1的分量。(给它们一个标识符，让我们在例子中称它们为A,B,C)
- 创建矩阵的副本
- 选择A。从A的所有"出口点"(被至少一个
0包围)到其他连接的组件(B,C)进行BFS。(BFS为最短路径，当然) - 现在在原始矩阵中，用(比如说)2标记这些点。
- 对B和C也重复上述2步。如果需要，可以用不同的路径标识符填充初始矩阵。(3为B, 4为C等)
现在，将图中连通的1视为节点，2、3等视为边。边的权值(很明显)是从一个节点到另一个节点的2、3等的个数。你现在可以使用Prims或Kruskals算法来形成这个图的MST。
对于k连通分量为1的(n * n)矩阵，该算法的复杂度为O(k * n * n) + O(k * k)。