Bubble shooter search alghoritm

So I have a Matrix of NxM. At a given position (for ex. [2][5]) I have a value which represents a color. If there is nothing at that point the value is -1. What I need to do is after I add a new point, to check all his neighbours with the same color value and if there are more than 2, set them all to -1.

If what I said doesn't make sense what I'm trying to do is an alghoritm which I use to destroy all the same color bubbles from my screen, where the bubbles are memorized in a matrix where -1 means no bubble and {0,1,2,...} represent that there is a bubble with a specific color.

This is what I tried and failed:

public class Testing {

static private int[][] gameMatrix=
{{3, 3, 4, 1, 1, 2, 2, 2, 0, 0},
{1, 4, 1, 4, 2, 2, 1, 3, 0, 0},
{2, 2, 4, 4, 3, 1, 2, 4, 0, 0},
{0, 1, 2, 3, 4, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
};

static int Rows=6;
static int Cols=10;
static int count;
static boolean[][] visited=new boolean[15][15];
static int NOCOLOR = -1;
static int color = 1;

public static void dfs(int r, int c, int color, boolean set)
{
for(int dr = -1; dr <= 1; dr++)
for(int dc = -1; dc <= 1; dc++)
if(!(dr == 0 && dc == 0) && ok(r+dr, c+dc))
{
int nr = r+dr;
int nc = c+dc;

// if it is the same color and we haven't visited this location before
if(gameMatrix[nr][nc] == color && !visited[nr][nc])
{
visited[nr][nc] = true;
count++;

dfs(nr, nc, color, set);

if(set)
{
gameMatrix[nr][nc] = NOCOLOR;
}
}
}
}

static boolean ok(int r, int c)
{
return r >= 0 && r < Rows && c >= 0 && c < Cols;
}

static void showMatrix(){
for(int i = 0; i < gameMatrix.length; i++) {
System.out.print("[");
for(int j = 0; j < gameMatrix[0].length; j++) {
System.out.print(" " + gameMatrix[i][j]);
}
System.out.println(" ]");
}
System.out.println();

}

static void putValue(int value,int row,int col){
gameMatrix[row][col]=value;
}

public static void main(String[] args){
System.out.println("Initial Matrix:");
putValue(1, 4, 1);
putValue(1, 5, 1);
showMatrix();

for(int n = 0; n < 15; n++)
for(int m = 0; m < 15; m++)
visited[n][m] = false;

//reset count
count = 0;
//dfs(bubbles.get(i).getRow(), bubbles.get(i).getCol(), color, false);

// get the contiguous count
dfs(5,1,color,false);
//if there are more than 2 set the color to NOCOLOR
for(int n = 0; n < 15; n++)
for(int m = 0; m < 15; m++)
visited[n][m] = false;
if(count > 2)
{
//dfs(bubbles.get(i).getRow(), bubbles.get(i).getCol(), color, true);
dfs(5,1,color,true);
}

System.out.println("Matrix after dfs:");
showMatrix();
}

}

• You should write more - what have failed? Give us some output :) – zacharmarz Feb 24 '12 at 9:26
• Well the matrix remains the same after dfs although it should set the some of the elements to -1. – Fofole Feb 24 '12 at 9:28
• ok I fixed it.:D – Fofole Feb 24 '12 at 9:36
• i am trying to implement same in objective C , but facing same issue. – Hemant Singh Rathore Oct 28 '13 at 18:19

What you need here is a depth first search.

  int R, C;
int[][] matrix;
int count;
boolean[][] visited;
int NOCOLOR = -1;
public int main()
{
int startR = 0;
int startC = 0;
int color = 1 // red
int R = 10;
int C = 20;

matrix = new int[R][C];
visited = new boolean[R][C];

matrix = LoadLevel(); // get a starting matrix with colors

//reset visited matrix to false.
for(int i = 0; i < R; i++)
for(int j = 0; j < C; j++)
visited[i][j] = false;

//reset count
count = 0;
dfs(startR, startC, color, false); // get the contiguous count

//if there are more than 2 set the color to NOCOLOR
if(count > 2)
{
dfs(startR, startC, color, true);
}
}

public void dfs(int r, int c, int color, boolean set)
{
for(int dr = -1; dr <= 1; dr++)
for(int dc = -1; dc <= 1; dc++)
if((dr == 0 ^ dc == 0) && ok(r+dr, c+dc)) // 4 neighbors
{
int nr = r+dr;
int nc = c+dc;

// if it is the same color and we haven't visited this location before
if(matrix[nr][nc] == color && !visited[nr][nc])
{
visited[nr][nc] = true;
count++;

dfs(nr, nc, color, set);

if(set)
{
matrix[nr][nc] = NOCOLOR;
}
}
}
}

boolean ok(int r, int c)
{
return r >= 0 && r < R && c >= 0 && c < C;
}

• Oh. Nice! With code and everything. After a first look this seems legit so good answer. I'll provide some feedback after trying it. – Fofole Feb 23 '12 at 16:30
• Please see my edit. :D – Luis Estrada Feb 23 '12 at 16:35
• You call dfs(nr, nc, color) need 1 more param :D – Fofole Feb 23 '12 at 16:48
• fixed recursive call parameter – Luis Estrada Feb 23 '12 at 16:51
• +1. Be aware that recursive functions can hit performance due to the ongoing assignment of stack frames at each recursion level. You can easily modify the basic algorithm to use a stack data structure to take the place of the system stack, see this. But I wouldn't change it unless you've profiled and seen that this is impacting performance more than a little. – Engineer Feb 24 '12 at 17:50

I think it would be easy to implement BFS or DFS to search same colors. You can just go to all of it's neighbours and then to their neighbours (if they are of the same color) etc.

So you will create graph, where every point is connected to its four- (or eight-) neighborhood.