目录
1. 图像渲染
1.1 算法原理
在本专题之前, 对于 FloodFill 算法, 我们就已经使用 DFS 的形式求解过了.
BFS 与 DFS 解题的核心思想是相同的, 都是找到 性质相同的连通块.
但 BFS 与 DFS 不同的是:
- DFS 是一条路走到黑, 一旦发现某个方向上可以走, 就一直沿着那个方向往下走, 等到不能再走时才会回头. (深搜递归)
- BFS 是一层一层的剥开, 把当前节点位置上的所有方向都看一遍, 记录满足条件的位置, 才往下一个位置上走 (宽搜队列)
1.2 算法代码
class Solution {
int oldColor;
int[] dx = new int[]{-1, 1, 0, 0};
int[] dy = new int[]{0, 0, -1, 1};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
if(image[sr][sc] == color) return image;
int m = image.length, n = image[0].length;
oldColor = image[sr][sc];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{sr, sc});
while(!q.isEmpty()) {
int[] arr = q.poll();
int a = arr[0], b = arr[1];
image[a][b] = color;
for(int k = 0; k < 4; k++) {
int x = a + dx[k];
int y = b + dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == oldColor) {
q.offer(new int[]{x, y});
}
}
}
return image;
}
}2. 岛屿数量
2.1 算法原理
本题依旧采用 BFS 的思想, 需要注意的是, 不能重复访问同一个位置.
避免相同位置的重复访问, 有以下两种方式避免:
- 访问完后, 修改原来的值(会导致原数组中的值被改变)
- 设置布尔类型的变量, 访问完后, 标记一下(采用)
2.2 算法代码
class Solution {
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
boolean[][] check;
int m, n;
int ret;
public int numIslands(char[][] grid) {
m = grid.length;
n = grid[0].length;
check = new boolean[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == '1' && !check[i][j]) {
ret++;
bfs(grid, i, j);
}
}
}
return ret;
}
public void bfs(char[][] grid, int i, int j) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{i, j});
check[i][j] = true;
while(!q.isEmpty()) {
int[] tmp = q.poll();
int a = tmp[0], b = tmp[1];
for(int k = 0; k < 4; k++) {
int x = a + dx[k], y = b + dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == '1') {
q.offer(new int[]{x, y});
check[x][y] = true;
}
}
}
}
}3. 岛屿的最大面积
3.1 算法原理
解题思路与上题相同, 只需使用变量额外的记录一下岛屿的面积即可.
返回所有岛屿中最大的面积.
3.2 算法代码
class Solution {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
boolean[][] check;
int m, n;
int ret;
public int maxAreaOfIsland(int[][] grid) {
m = grid.length; n = grid[0].length;
check = new boolean[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1 && !check[i][j]) {
ret = Math.max(bfs(grid, i, j), ret);
}
}
}
return ret;
}
public int bfs(int[][] grid, int i, int j) {
int count = 1;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{i, j});
check[i][j] = true;
while(!q.isEmpty()) {
int[] tmp = q.poll();
int a = tmp[0], b = tmp[1];
for(int k = 0; k < 4; k++) {
int x = a + dx[k], y = b + dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == 1) {
count++;
check[x][y] = true;
q.offer(new int[]{x, y});
}
}
}
return count;
}
}4. 被围绕的区域
4.1 算法原理
核心: 正难则反
- 使用布尔变量, 标记边界情况下的 'O'.
- 将非标记的字符全部修改为 'X'
4.2 算法代码
class Solution {
// 正难则反
int m, n;
boolean[][] check;
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
public void solve(char[][] board) {
m = board.length; n = board[0].length;
check = new boolean[m][n];
// 处理边界上的 'O'
for(int i = 0; i < m; i++) {
if(board[i][0] == 'O' && !check[i][0]) bfs(board, i, 0);
if(board[i][n - 1] == 'O' && !check[i][n - 1]) bfs(board, i, n - 1);
}
for(int j = 0; j < n; j++) {
if(board[0][j] == 'O' && !check[0][j]) bfs(board, 0, j);
if(board[m - 1][j] == 'O' && !check[m - 1][j]) bfs(board, m - 1, j);
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(!check[i][j]) board[i][j] = 'X';
}
}
}
public void bfs(char[][] board, int i, int j) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{i, j});
check[i][j] = true;
while(!q.isEmpty()) {
int[] tmp = q.poll();
int a = tmp[0], b = tmp[1];
for(int k = 0; k < 4; k++) {
int x = a + dx[k], y = b + dy[k];
if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !check[x][y]) {
check[x][y] = true;
q.offer(new int[]{x, y});
}
}
}
}
}END
标签：int,FloodFill,BFS,算法,grid,board,&&,new,check From： https://blog.csdn.net/2401_83595513/article/details/143573723