# 算法细节系列（19）：广度搜索优先

## Leetcode 407 Trapping Rain Water II

```    private class Cell{
int row;
int col;
int height;
public Cell(int row, int col, int height){
this.row = row;
this.col = col;
this.height = height;
}
}

public int trapRainWater(int[][] heightMap) {
int row = heightMap.length;
if (row <= 2) return 0;
int col = heightMap[0].length;
if (col <= 2) return 0;

int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};

PriorityQueue<Cell> queue = new PriorityQueue<>(1,new Comparator<Cell>(){
@Override
public int compare(Cell o1, Cell o2) {
return o1.height - o2.height;
}
});
boolean[][] visited = new boolean[row][col];
for (int i = 0; i < row; i++){
visited[i][0] = true;
visited[i][col-1] = true;
queue.offer(new Cell(i, 0, heightMap[i][0]));
queue.offer(new Cell(i, col-1, heightMap[i][col-1]));
}

for (int i = 0; i < col; i++){
visited[0][i] = true;
visited[row-1][i] = true;
queue.offer(new Cell(0, i, heightMap[0][i]));
queue.offer(new Cell(row-1, i, heightMap[row-1][i]));
}

int area = 0;
while (!queue.isEmpty()){
Cell cell = queue.poll();
for (int[] d : dir){
int nrow = cell.row + d[0];
int ncol = cell.col + d[1];
if (nrow >=0 && nrow < row && ncol >= 0 && ncol < col && !visited[nrow][ncol]){
visited[nrow][ncol] = true;
area += Math.max(0, cell.height-heightMap[nrow][ncol]);
queue.offer(new Cell(nrow, ncol, Math.max(heightMap[nrow][ncol], cell.height)));
}
}
}
return area;
}```

## Leetcode 310 Minimum Height Trees

```    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);

for (int[] edge : edges) {
}

List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; ++i)

while (n > 2) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int i : leaves) {
}
leaves = newLeaves;
}
return leaves;
}```

## Leetcode 130 Surrounded Regions

```    public void solve(char[][] board) {

int row = board.length;
if (row == 0) return;
int col = board[0].length;
if (col == 0) return;

boolean[][] canNotTurn = new boolean[row][col];
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O') {
queue.offer(new int[] { i, 0 });
canNotTurn[i][0] = true;
}
if (board[i][col - 1] == 'O') {
queue.offer(new int[] { i, col - 1 });
canNotTurn[i][col-1] = true;
}
}

for (int j = 1; j < col - 1; j++) {
if (board[0][j] == 'O') {
queue.offer(new int[] { 0, j });
canNotTurn[0][j] = true;
}
if (board[row - 1][j] == 'O') {
queue.offer(new int[] { row - 1, j });
canNotTurn[row-1][j] = true;
}
}

int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
while(!queue.isEmpty()){
int[] curr = queue.poll();
for (int[] d : dir){
int nrow = curr[0] + d[0];
int ncol = curr[1] + d[1];
if (nrow >= 0 && nrow < row && ncol >= 0 && ncol < col && board[nrow][ncol] == 'O' && !canNotTurn[nrow][ncol]){
queue.offer(new int[]{nrow, ncol});
canNotTurn[nrow][ncol] = true;
}
}
}

for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (!canNotTurn[i][j] && board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}```

0 条评论

• ### 挑战程序竞赛系列（31）：4.5剪枝

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（30）：3.4矩阵的幂

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### POJ 刷题系列：1083. Moving Tables

POJ 刷题系列：1083. Moving Tables 传送门：POJ 1083. Moving Tables 题意： 一条走廊，两栏房间。搬运工每次从房价...

• ### AtCoder Beginner Contest 174 A ~ E

我看有人用指针来做的，其实道理是一样的，就是字符串中所有的R都在左边，然后所有的W都在右边就行了。

• ### POJ 1845-Sumdiv（厉害了这个题）

Consider two natural numbers A and B. Let S be the sum of all natural divisors o...

• ### 数独终盘生成的几种方法

为了完成矩阵的转换，我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成：

• ### 1089 狼人杀-简单版 (20 分)

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### 挑战程序竞赛系列（31）：4.5剪枝

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...