CODEWITHSUNDEEP
javaalgorithmmultidimensional-array
Mina Saleh
Mina Saleh

Reputation: 53

connected neighbours in a java 2d array

I'm designing an engine for a game which has a 2D 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'm stuck at the "game over" condition as it has to check if the 1's or 2's are connected. It should declare the player with 1's as winner and return this:

 1 1
 1   1 1
1  1
1
  1
    1

I've tried using recursion by checking every position in the array and checking its neighbors in all 8 directions but the method took 45 seconds to run which is inefficient.

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

Upvotes: 5

Views: 3393

Answers (5)

MissingNumber
MissingNumber

Reputation: 1182

Go ahead and make a duplicate graph a[n][n] with a[i][j] = 1 if i and j are connected.

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

So once you have done mapping count of nodes in a network with one of its node .

You'll find value count and if count == total_no_of_1's

If so then network 1 is connected .if not then same with 2's and and declare result .

Upvotes: 0

smttsp
smttsp

Reputation: 4191

What you need is that:

Connected_component_labeling

This gives a pseudo code,

hope it helps

Upvotes: 2

st0le
st0le

Reputation: 33545

Maintain a UnionFind data structure from the beginning, each entry representing each cell. Initially, perform a Union on adjacent cells with the same values. When a player marks a cell, perform a union() with the adjacent cells if the value is the same as the player's value. In the Union find, you can keep track of the number of cells that have a value, when that number is equal to the number of times that value was inserted, you have a winner.

You also do it Linearly using the algorithm described here

Upvotes: 0

akostadinov
akostadinov

Reputation: 18594

This question is not so easy. It looks to me you can look at your matrix as a graph and you try to find out if your graph is connected. i.e. is the graph of 1s connected and is the graph of 2s connected. Here you see a few algorithms. Since you are creating the graph you can also keep track of the groups of nodes a player is creating and upon creating a new node, you can check to how many groups is the new node connected and union whatever get connected by the new node (or create a new group containing your new node if it does not connect anything).

btw you can convert any recursion to a loop but this should be necessary only if your stack gets exhausted.

Upvotes: 0

Lone nebula
Lone nebula

Reputation: 4878

Here are some tips:

  • If possible, keep track of how many 1's and 2's there are from the beginning.
  • When checking if they're connected, you could use a boolean matrix and a counter, to keep track of which ones you've already checked and how many of them.
  • Use recursion on the necessary neighbors instead of checking every position in the matrix.

Upvotes: 1

Related Questions