英文:
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 < 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
看这个代码块：
for (int index = 0;index < 4;index++){
row = row+tb_neighbour[index];
col = col+lr_neighbour[index];
}
假设 row = 2，col = 1...
然后在第一次迭代中，你这样做：row = 2 + 1 = 3，col = 1 + 0 = 1... 现在你的 row 和 col 值已经改变了...
在第二次迭代中，你得到：row = 3 + -1 = 2，col = 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 < 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 < 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;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论