Количество ячеек с одинаковым значением Использование BFS - PullRequest
Новая
       71

Количество ячеек с одинаковым значением Использование BFS

1 голос
/ 02 мая 2020

Привет всем, я пытаюсь решить проблему, в которой мне нужно найти количество ячеек с одинаковым значением, учитывая, что я могу перемещаться вверх и вниз влево и вправо в матрице. Я знаю, что могу решить это с помощью bfs. Но я не получаю правильный ответ, например, 

 int[][] matrix = {

  {2 , 3, 4, 10, 12},
  {20 , 30, 14, 11, 13},
  {29 , 39, 40, 12, 24},
  {40 , 39, 39, 15, 35},
  {100 ,23, 24, 60, 80}
  };

Это должно вернуть 3, потому что если я начну с ячейки (2,1), я получу 39,39,39, двигаясь вверх, вниз, влево и вправо, и мой метод выглядит как find_cells (int [] [] matrix, int row, int col), где row и col являются начальными точками. Не используйте вспомогательный метод. Я получаю 1, может быть потому, что я отмечаю Соседи как истина, и в следующий раз, когда я пытаюсь получить к ним доступ, они пропускают их. Извините за отступ. 

     public int find_cells(int[][] matrix, int row, int col){
         //invalid row and col
        if (row < 0 | col < 0 | row > matrix.length | col > matrix[0].length)
              return -1;


        // check if cell is already visited.
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];

        //left and right neighbours
       int[] lr_neighbour = {0, 0, -1,1};
       //top and bottom neighbours
       int[] tb_neighbour = {1, -1, 0, 0};

       //number of same cells
       int modified = 0;

      //queue
       Queue<Integer> queue = new LinkedList<>();
       queue.add(matrix[row][col]);
      //mark current cell as visited.
       visited[row][col] = true;

      //current pixel at (row,col)
      int current_cell = matrix[row][col];

     while (!queue.isEmpty()){
        queue.remove();
        for (int index = 0;index < 4;index++){
            row = row+tb_neighbour[index];
            col = col+lr_neighbour[index];
            if (row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length || visited[row][col])
                continue;
            if (current_cell == matrix[row][col]){
                //mark all other valid cells as visited.
                queue.add(matrix[row][col]);
                modified++;
            }
            visited[row][col] = true;
        }
    }

       return modified;
}

1 Ответ

1 голос
/ 02 мая 2020

Посмотрите на этот блок: 

for (int index = 0;index < 4;index++){
            row = row+tb_neighbour[index];
            col = col+lr_neighbour[index];

Позволяет row = 2 col = 1 ....

, затем на 1-й итерации вы делаете это: row = 2 + 1 = 3, col = 1 + 0 = 1 ... теперь значение строки и столбца изменилось ..

На 2-й итерации вы получаете: row = 3 + -1 = 2, col = 1 + 0 = 1 ... ... это неправильно ..

Возьмите новую переменную и pu sh строку и столбец в очереди ...

Попробуйте с этим: 

public int find_cells(int[][] matrix, int row, int col){
        //invalid row and col
        if (row < 0 | col < 0 | row > matrix.length | col > matrix[0].length)
            return -1;


        // check if cell is already visited.
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];

        //left and right neighbours
        int[] lr_neighbour = {0, 0, -1,1};
        //top and bottom neighbours
        int[] tb_neighbour = {1, -1, 0, 0};

        //number of same cells
        int modified = 0;

        //queue
        Queue<Integer> queue = new LinkedList<>();
        queue.add(row);
        queue.add(col);
        //mark current cell as visited.
        visited[row][col] = true;

        //current pixel at (row,col)
        int current_cell = matrix[row][col];
        int x,y;
        while (!queue.isEmpty()){
            row = queue.remove();
            col = queue.remove();
            for (int index = 0;index < 4;index++){
                x = row+tb_neighbour[index];
                y = col+lr_neighbour[index];
                if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length || visited[x][y])
                    continue;
                if (current_cell == matrix[x][y]){
                    //mark all other valid cells as visited.
                    queue.add(x);
                    queue.add(y);
                    modified++;
                }
                visited[x][y] = true;
            }
        }

        return modified;
    }
...