大家好,我正在尝试解决一个问题,我必须找到具有相同值的像元数,因为我只能在矩阵中左右移动。我知道我可以使用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 [] []矩阵, int row,int col)其中row和col是起点。不要使用任何辅助方法。我得到1可能是因为我将邻居标记为true,下次我尝试访问它们时会跳过它们。抱歉,缩进。
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;
}
查看此块:
for (int index = 0;index < 4;index++){
row = row+tb_neighbour[index];
col = col+lr_neighbour[index];
让行= 2列= 1 ....
然后在第一次迭代中,将其设置为:row = 2 + 1 = 3,col = 1 + 0 = 1 ...现在,您的行和col值已更改。
在第2次迭代中,您得到:row = 3 + -1 = 2,col = 1 + 0 = 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(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;
}