FloodFill算法
文章目录
- 1. 图像渲染（733）
- 2. 岛屿数量（200）
- 3. 岛屿的最大面积（695）
- 4. 被围绕的区域（130）
1. 图像渲染（733）
题目描述：
算法原理：
根据题意我们需要将与最初选定的值相等的格子的值全部更改为指定的color值（包含最初选定的格子），这里我们就可以分为两种情况，第一种情况就是最初选定的格子中的值就是等于color值，那么我们就无需去操作了直接返回image数组；第二种情况就是color不等于最初选定的格子中的值，此时我们建立队列并且将最初的格子的坐标入队，然后沿着上下左右的方向进行发散，如果发散的坐标满足在数组内的条件并且值是等于最初选定的格子中的值，那么就将它的值改为color，然后不断地去循环，直至队列为空。
代码如下：
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int prev = image[sr][sc];
if (prev == color) {
return image;
}
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { sr, sc });
int[] dx = { 1, -1, 0, 0 };
int[] dy = { 0, 0, 1, -1 };
int m = image.length, n = image[0].length;
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int i = temp[0], j = temp[1];
image[i][j] = color;
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < m && x >= 0 && y >= 0 && y < n && image[x][y] == prev) {
queue.add(new int[] { x, y });
}
}
}
return image;
}
}
题目链接
2. 岛屿数量（200）
题目描述：
算法原理：
这题实际上就是在上一题的基础上去加了循环遍历。首先我们去遍历数组，设定一个记录岛屿数量的变量ret，当我们遍历到数组元素等于1时的格子并且这个格子还未被扩散到时（是否扩散到由布尔类型数组记录），ret++，并且此时开始从这个坐标来从四个方向扩散，操作和上一题一样，后面的遍历的格子也是一样的操作。这样最终的ret就是记录的岛屿的数量，返回ret即可。
代码如下：
class Solution {
int m, n;
boolean[][] vis;
int[] dx = { 0, 0, 1, -1 };
int[] dy = { 1, -1, 0, 0 };
public int numIslands(char[][] grid) {
int ret = 0;
m = grid.length;
n = grid[0].length;
vis = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !vis[i][j]) {
bfs(grid, i, j);
ret++;
}
}
}
return ret;
}
public void bfs(char[][] grid, int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { i, j });
vis[i][j] = true;
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int a = temp[0], b = temp[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 && !vis[x][y] && grid[x][y] == '1') {
queue.add(new int[] { x, y });
vis[x][y] = true;
}
}
}
}
}
题目链接
3. 岛屿的最大面积（695）
题目描述：
算法原理：
这题和上一题的思路一致，只不过需要在bfs函数当中计算发散出的格子的个数并返回。
代码如下：
class Solution {
int m, n;
boolean[][] vis;
int[] dx = { 1, -1, 0, 0 };
int[] dy = { 0, 0, 1, -1 };
public int maxAreaOfIsland(int[][] grid) {
m = grid.length;
n = grid[0].length;
vis = new boolean[m][n];
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !vis[i][j]) {
ret = Math.max(bfs(grid, i, j), ret);
}
}
}
return ret;
}
public int bfs(int[][] grid, int i, int j) {
int ret = 1;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { i, j });
vis[i][j] = true;
while (!queue.isEmpty()) {
int[] tmp = queue.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 && !vis[x][y] && grid[x][y] == 1) {
queue.add(new int[] { x, y });
vis[x][y] = true;
ret++;
}
}
}
return ret;
}
}
题目链接
4. 被围绕的区域（130）
题目描述：
算法原理：
我们发现要是像之前那样采用直接发散的做法是很困难的，因为发散的过程中肯定是要将’O’这样的格子给置为’X’，后面比如说我们碰到在数组边缘的’O’就很难处理了。所以我们正难则反，因为和数组边缘的’O’相连的’O’都是不需要去变为’X’的，所以我们先找一下数组中边缘部分的’O’，然后发散，将这些部分全部置为’Y’，之后我们再去遍历数组，碰到’O’就置为’X’，之后我们再将所有的’Y’还原回’O’，一下子简化问题。
代码如下：
class Solution {
int m, n;
int[] dx = { 1, -1, 0, 0 };
int[] dy = { 0, 0, 1, -1 };
public void solve(char[][] board) {
m = board.length;
n = board[0].length;
for (int i = 0; i < n; i++) {
if (board[0][i] == 'O') {
bfs(board, 0, i);
}
if (board[m - 1][i] == 'O') {
bfs(board, m - 1, i);
}
}
for (int i = 1; i < m - 1; i++) {
if (board[i][0] == 'O') {
bfs(board, i, 0);
}
if (board[i][n - 1] == 'O') {
bfs(board, i, n - 1);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'Y') {
board[i][j] = 'O';
}
}
}
}
public void bfs(char[][] board, int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { i, j });
board[i][j] = 'Y';
while (!queue.isEmpty()) {
int[] tmp = queue.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') {
queue.add(new int[] { x, y });
board[x][y] = 'Y';
}
}
}
}
}
题目链接