6
\$\begingroup\$

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();
    }

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

2 Answers 2

7
\$\begingroup\$

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;
    }
\$\endgroup\$
11
  • \$\begingroup\$ Oh. Nice! With code and everything. After a first look this seems legit so good answer. I'll provide some feedback after trying it. \$\endgroup\$
    – Fofole
    Feb 23, 2012 at 16:30
  • \$\begingroup\$ Please see my edit. :D \$\endgroup\$ Feb 23, 2012 at 16:35
  • \$\begingroup\$ You call dfs(nr, nc, color) need 1 more param :D \$\endgroup\$
    – Fofole
    Feb 23, 2012 at 16:48
  • \$\begingroup\$ fixed recursive call parameter \$\endgroup\$ Feb 23, 2012 at 16:51
  • 2
    \$\begingroup\$ +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. \$\endgroup\$
    – Engineer
    Feb 24, 2012 at 17:50
1
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .