在java 2d数组中连接的邻居

Question

我正在设计一个游戏引擎,它有一个像这样的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秒才能运行,这是低效的.

有没有人有任何想法？一个伪代码示例将被赞赏(我是一个慢学习者).

Answer 1

继续制作一个复制图，如果 和a[n][n]是a[i][j] = 1相连的。ij

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

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
    }
}

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

你会发现值计数并且如果计数==total_no_of_1's

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