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

huangapple go评论104阅读模式
英文:

Number of cells with same value Using bfs

问题

  1. public int find_cells(int[][] matrix, int row, int col) {
  2. if (row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length)
  3. return -1;
  4. boolean[][] visited = new boolean[matrix.length][matrix[0].length];
  5. int[] lr_neighbour = {0, 0, -1, 1};
  6. int[] tb_neighbour = {1, -1, 0, 0};
  7. int modified = 0;
  8. Queue<Integer> queue = new LinkedList<>();
  9. queue.add(matrix[row][col]);
  10. visited[row][col] = true;
  11. int current_cell = matrix[row][col];
  12. while (!queue.isEmpty()) {
  13. queue.remove();
  14. for (int index = 0; index < 4; index++) {
  15. int newRow = row + tb_neighbour[index];
  16. int newCol = col + lr_neighbour[index];
  17. if (newRow < 0 || newCol < 0 || newRow >= matrix.length || newCol >= matrix[0].length || visited[newRow][newCol])
  18. continue;
  19. if (current_cell == matrix[newRow][newCol]) {
  20. queue.add(matrix[newRow][newCol]);
  21. modified++;
  22. }
  23. visited[newRow][newCol] = true;
  24. }
  25. }
  26. return modified;
  27. }
英文:

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

  1. int[][] matrix = {
  2. {2 , 3, 4, 10, 12},
  3. {20 , 30, 14, 11, 13},
  4. {29 , 39, 40, 12, 24},
  5. {40 , 39, 39, 15, 35},
  6. {100 ,23, 24, 60, 80}
  7. };

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.

  1. public int find_cells(int[][] matrix, int row, int col){
  2. //invalid row and col
  3. if (row &lt; 0 | col &lt; 0 | row &gt; matrix.length | col &gt; matrix[0].length)
  4. return -1;
  5. // check if cell is already visited.
  6. boolean[][] visited = new boolean[matrix.length][matrix[0].length];
  7. //left and right neighbours
  8. int[] lr_neighbour = {0, 0, -1,1};
  9. //top and bottom neighbours
  10. int[] tb_neighbour = {1, -1, 0, 0};
  11. //number of same cells
  12. int modified = 0;
  13. //queue
  14. Queue&lt;Integer&gt; queue = new LinkedList&lt;&gt;();
  15. queue.add(matrix[row][col]);
  16. //mark current cell as visited.
  17. visited[row][col] = true;
  18. //current pixel at (row,col)
  19. int current_cell = matrix[row][col];
  20. while (!queue.isEmpty()){
  21. queue.remove();
  22. for (int index = 0;index &lt; 4;index++){
  23. row = row+tb_neighbour[index];
  24. col = col+lr_neighbour[index];
  25. if (row &lt; 0 || col &lt; 0 || row &gt;= matrix.length || col &gt;= matrix[0].length || visited[row][col])
  26. continue;
  27. if (current_cell == matrix[row][col]){
  28. //mark all other valid cells as visited.
  29. queue.add(matrix[row][col]);
  30. modified++;
  31. }
  32. visited[row][col] = true;
  33. }
  34. }
  35. return modified;
  36. }

答案1

得分: 1

看这个代码块:

  1. for (int index = 0;index < 4;index++){
  2. row = row+tb_neighbour[index];
  3. col = col+lr_neighbour[index];
  4. }
  5. 假设 row = 2col = 1...
  6. 然后在第一次迭代中你这样做row = 2 + 1 = 3col = 1 + 0 = 1... 现在你的 row col 值已经改变了...
  7. 在第二次迭代中你得到row = 3 + -1 = 2col = 1 + 0 = 1... 这是错误的...
  8. 使用新变量并将 row col 推入队列...
  9. 尝试使用以下内容
  10. ```java
  11. public int find_cells(int[][] matrix, int row, int col){
  12. //无效的行和列
  13. if (row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length)
  14. return -1;
  15. //检查单元格是否已经访问过。
  16. boolean[][] visited = new boolean[matrix.length][matrix[0].length];
  17. //左右相邻
  18. int[] lr_neighbour = {0, 0, -1, 1};
  19. //上下相邻
  20. int[] tb_neighbour = {1, -1, 0, 0};
  21. //相同单元格的数量
  22. int modified = 0;
  23. //队列
  24. Queue<Integer> queue = new LinkedList<>();
  25. queue.add(row);
  26. queue.add(col);
  27. //标记当前单元格已访问。
  28. visited[row][col] = true;
  29. //当前像素位于(row,col)
  30. int current_cell = matrix[row][col];
  31. int x, y;
  32. while (!queue.isEmpty()){
  33. row = queue.remove();
  34. col = queue.remove();
  35. for (int index = 0;index < 4;index++){
  36. x = row + tb_neighbour[index];
  37. y = col + lr_neighbour[index];
  38. if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length || visited[x][y])
  39. continue;
  40. if (current_cell == matrix[x][y]){
  41. //标记所有其他有效单元格为已访问。
  42. queue.add(x);
  43. queue.add(y);
  44. modified++;
  45. }
  46. visited[x][y] = true;
  47. }
  48. }
  49. return modified;
  50. }
英文:

Look at this block:

  1. for (int index = 0;index &lt; 4;index++){
  2. row = row+tb_neighbour[index];
  3. 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:

  1. public int find_cells(int[][] matrix, int row, int col){
  2. //invalid row and col
  3. if (row &lt; 0 | col &lt; 0 | row &gt; matrix.length | col &gt; matrix[0].length)
  4. return -1;
  5. // check if cell is already visited.
  6. boolean[][] visited = new boolean[matrix.length][matrix[0].length];
  7. //left and right neighbours
  8. int[] lr_neighbour = {0, 0, -1,1};
  9. //top and bottom neighbours
  10. int[] tb_neighbour = {1, -1, 0, 0};
  11. //number of same cells
  12. int modified = 0;
  13. //queue
  14. Queue&lt;Integer&gt; queue = new LinkedList&lt;&gt;();
  15. queue.add(row);
  16. queue.add(col);
  17. //mark current cell as visited.
  18. visited[row][col] = true;
  19. //current pixel at (row,col)
  20. int current_cell = matrix[row][col];
  21. int x,y;
  22. while (!queue.isEmpty()){
  23. row = queue.remove();
  24. col = queue.remove();
  25. for (int index = 0;index &lt; 4;index++){
  26. x = row+tb_neighbour[index];
  27. y = col+lr_neighbour[index];
  28. if (x &lt; 0 || y &lt; 0 || x &gt;= matrix.length || y &gt;= matrix[0].length || visited[x][y])
  29. continue;
  30. if (current_cell == matrix[x][y]){
  31. //mark all other valid cells as visited.
  32. queue.add(x);
  33. queue.add(y);
  34. modified++;
  35. }
  36. visited[x][y] = true;
  37. }
  38. }
  39. return modified;
  40. }

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

发表评论

匿名网友

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

确定