5

我正在为具有这样的 2D 数组的游戏设计一个引擎：

0,1,1,2,0
0,1,2,1,1
1,0,1,0,2
2,1,2,0,0
2,0,1,0,0

我被困在“游戏结束”状态，因为它必须检查 1 或 2 是否已连接。它应该宣布拥有 1 的玩家为获胜者并返回：

 1 1
 1   1 1
1  1
1
  1
    1

我尝试通过检查数组中的每个位置并在所有 8 个方向上检查其邻居来使用递归，但该方法需要 45 秒才能运行，这是低效的。

有没有人有任何想法？一个伪代码示例将不胜感激（我是一个缓慢的学习者）。

4

5 回答 5

2

你需要的是：

Connected_component_labeling

这给出了一个伪代码，

希望能帮助到你

于 2013-04-16T16:12:13.273 回答
1

以下是一些提示：

  • 如果可能，从一开始就记录有多少个 1 和 2。
  • 在检查它们是否已连接时，您可以使用boolean矩阵和计数器来跟踪您已经检查过哪些以及其中有多少。
  • 对必要的邻居使用递归，而不是检查矩阵中的每个位置。
于 2013-04-16T12:46:33.020 回答
0

从一开始就维护一个UnionFind数据结构，每个条目代表每个单元格。最初，对具有相同值的相邻单元格执行联合。当玩家标记一个单元格时，如果值与玩家的值相同，则与相邻单元格执行 union()。在联合查找中，您可以跟踪具有值的单元格的数量，当该数量等于插入该值的次数时，您就有了获胜者。

您还可以使用此处描述的算法线性地执行此操作

于 2013-04-16T14:17:20.117 回答
0

这个问题并不容易。在我看来，您可以将矩阵视为图形，然后尝试确定图形是否已连接。ie 是 1s 连接的图，是 2s 连接的图。在这里您可以看到一些算法。由于您正在创建图表，因此您还可以跟踪玩家正在创建的节点组，并在创建新节点时，您可以检查新节点连接了多少组，并联合新节点连接的任何内容（或如果它没有连接任何东西，则创建一个包含新节点的新组）。

顺便说一句，您可以将任何递归转换为循环，但只有当您的堆栈耗尽时才需要这样做。

于 2013-04-16T13:18:45.350 回答
0

继续，a[n][n]用a[i][j] = 1ifi和jare connected 制作一个重复的图表。

然后您可以执行以下操作：

int count = 0;

void dfs(int i)
{
    int k;
    for(k = 0; k < n; k++)
    {
        if(A[i][k] == 1 && !visited[k])
        {
            count++;
            visited[k] = 1;
            dfs(k);
        }
    }
}

for(i=0; i < n;i++)
{
    if(!visited[i])
    {
        count=1;
        visited[i]=1;
        dfs(i);
        // map i with count .. here
    }
}

因此，一旦您完成了网络中的节点数与其节点之一的映射。

你会发现价值计数，如果 count == total_no_of_1's

如果是这样，则网络 1 已连接。如果不是，则与 2 相同，并声明结果。

于 2013-04-16T14:30:44.767 回答