Глубина первой поисковой ошибки?

Question

Итак, у меня есть матрица N × M.В данной позиции у меня есть значение, которое представляет цвет.Если в этот момент ничего нет, значение равно -1.Что мне нужно сделать, так это после того, как я добавлю новую точку, чтобы проверить всех его соседей с одинаковым значением цвета, и если их больше 2, установите их все на -1.

Если то, что я сказал, нене имеет смысла то, что я пытаюсь сделать, это алгоритм, который я использую, чтобы уничтожить все те же цветные пузыри с моего экрана, где пузыри запоминаются в матрице, где -1 означает отсутствие пузыря, а {0,1,2,...} означает, чтоэто пузырь с определенным цветом.

Также, если у вас есть какие-либо предложения, я буду благодарен.Благодарю.Вот что я попробовал и потерпел неудачу:

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, 4, 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);
        putValue(1, 4, 2);
        showMatrix();

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

        //reset count
        count = 0;
        dfs(5,1,color,false);
        //if there are more than 2 set the color to NOCOLOR
        for(int n = 0; n < Rows; n++)
            for(int m = 0; m < Cols; m++)
                visited[n][m] = false;
        if(count > 2)
        {
            dfs(5,1,color,true);
        }
        System.out.println("Matrix after dfs:");
        showMatrix();
    }

}

Answer 1

Я думаю, что вы после алгоритма заливки (возможно, с немного странным ограничением, что должно быть как минимум два соседа одного цвета)?Я не уверен, почему поиск в глубину здесь уместен.

Answer 2

Одна проблема, с которой вы сталкиваетесь, заключается в том, что вы не проверяете верхний ряд и столбец левого теста:

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

вам следует проверить r >= 0, c>= 0

Вторая проблемавы используете dfs() дважды, но поле visited является статическим - оно все установлено на true перед вторым запуском dfs(), вам нужно инициализировать его обратно на false ввсе поля перед вторым запуском, иначе алгоритм немедленно прекратит работу, ничего не делая [поскольку все узлы уже находятся в visited - и алгоритм примет решение не повторно исследовать эти узлы.].

Answer 3

Ваш код также считает диагональные ячейки соседями.Если вам нужны только левые / правые / верхние / нижние ячейки, тогда вы можете проверить

if(!(dr == 0 && dc == 0) && ok(r+dr, c+dc) && dr * dc == 0)

Вам также необходимо сосчитать первую ячейку.Вы не учитываете ячейку, с которой начинаете.