相同值的单元格数量使用广度优先搜索

huangapple 未分类评论48阅读模式
英文:

Number of cells with same value Using bfs

问题

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

    boolean[][] visited = new boolean[matrix.length][matrix[0].length];

    int[] lr_neighbour = {0, 0, -1, 1};
    int[] tb_neighbour = {1, -1, 0, 0};

    int modified = 0;

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

    int current_cell = matrix[row][col];

    while (!queue.isEmpty()) {
        queue.remove();
        for (int index = 0; index < 4; index++) {
            int newRow = row + tb_neighbour[index];
            int newCol = col + lr_neighbour[index];
            if (newRow < 0 || newCol < 0 || newRow >= matrix.length || newCol >= matrix[0].length || visited[newRow][newCol])
                continue;
            if (current_cell == matrix[newRow][newCol]) {
                queue.add(matrix[newRow][newCol]);
                modified++;
            }
            visited[newRow][newCol] = true;
        }
    }
    return modified;
}
英文:

Hi everyone i'm trying to solve a problem where i have to find the number of cells that have same value given i can only move up down left and right in a matrix.I know i can solving it using bfs .But i'm not getting correct answer so for example

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

This should return 3 because if i will start from cell (2,1) i'll get 39,39,39 by moving up, down ,left and right and my method looks like find_cells(int[][] matrix, int row, int col) where row and col are starting points.Do not use any helper method.I'm getting 1 may be because i'm marking the neighbors as true and next time when i try to access them it skips them.Sorry for the indentation.

     public int find_cells(int[][] matrix, int row, int col){
         //invalid row and col
        if (row &lt; 0 | col &lt; 0 | row &gt; matrix.length | col &gt; 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&lt;Integer&gt; queue = new LinkedList&lt;&gt;();
       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 &lt; 4;index++){
            row = row+tb_neighbour[index];
            col = col+lr_neighbour[index];
            if (row &lt; 0 || col &lt; 0 || row &gt;= matrix.length || col &gt;= 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

看这个代码块:

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

假设 row = 2col = 1...

然后在第一次迭代中你这样做row = 2 + 1 = 3col = 1 + 0 = 1... 现在你的 row 和 col 值已经改变了...

在第二次迭代中你得到row = 3 + -1 = 2col = 1 + 0 = 1... 这是错误的...

使用新变量并将 row 和 col 推入队列...

尝试使用以下内容

```java
public int find_cells(int[][] matrix, int row, int col){
    //无效的行和列
    if (row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length)
        return -1;

    //检查单元格是否已经访问过。
    boolean[][] visited = new boolean[matrix.length][matrix[0].length];

    //左右相邻
    int[] lr_neighbour = {0, 0, -1, 1};
    //上下相邻
    int[] tb_neighbour = {1, -1, 0, 0};

    //相同单元格的数量
    int modified = 0;

    //队列
    Queue<Integer> queue = new LinkedList<>();
    queue.add(row);
    queue.add(col);
    //标记当前单元格已访问。
    visited[row][col] = true;

    //当前像素位于(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]){
                //标记所有其他有效单元格为已访问。
                queue.add(x);
                queue.add(y);
                modified++;
            }
            visited[x][y] = true;
        }
    }

    return modified;
}
英文:

Look at this block:

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

Lets row = 2 col = 1....

then at 1st iteration u make it : row = 2 + 1 = 3, col = 1 + 0 = 1... now your row and col value changed..

At 2nd iteration u get: row = 3 + -1 = 2, col = 1 + 0 = 1.... its wrong..

Take new variable and push row and column in queue...

Try with this:

public int find_cells(int[][] matrix, int row, int col){
        //invalid row and col
        if (row &lt; 0 | col &lt; 0 | row &gt; matrix.length | col &gt; 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&lt;Integer&gt; queue = new LinkedList&lt;&gt;();
        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 &lt; 4;index++){
                x = row+tb_neighbour[index];
                y = col+lr_neighbour[index];
                if (x &lt; 0 || y &lt; 0 || x &gt;= matrix.length || y &gt;= 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;
    }

huangapple
  • 本文由 发表于 2020年5月2日 15:16:22
  • 转载请务必保留本文链接:https://java.coder-hub.com/61555744.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定