Geek asks and answers

Related neighbors in java 2d array

I am developing a game engine with a two-dimensional array like this:

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

I am stuck in a “game” state because he needs to check if 1 or 2 are connected. He must declare the player with 1 winner and return him:

 1 1
 1   1 1
1  1
1
  1
    1

I tried using recursion by checking each position in the array and checking its neighbors in all 8 directions, but it took 45 seconds to complete this operation.

Does anyone have any ideas? The pseudo-code example will be appreciated (I'm a slow learner).

+5
source share
5 answers

We go and make a duplicate of graph a[n][n]c a[i][j] = 1, if iand are connected j.

Then you can do the following:

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

, node.

count count == total_no_of_1's

, 1 .if 2 .

0

:

  • , 1 2 .
  • , , boolean , , , .
  • .
+1

. , , , . 1s, 2s, . . , , , node , node , , new node ( , node, ).

btw , , .

0

Maintain the UnionFind data structure from the beginning, each record representing each cell. Initially connect to adjacent cells with the same values. When a player marks a cell, do union () with adjacent cells if the value matches the value of the player. In Union find, you can track the number of cells that have a value, when this number is equal to the number of times this value was inserted, you have a winner.

You also do this linearly using the algorithm described here

0
source

More articles:


All Articles