733. 图像渲染

有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一个新的颜色值 newColor,让你重新上色这幅图像。

为了完成上色工作,从初始坐标开始,记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

  • 示例:
1
2
3
4
输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
  • 解析:
1
2
在图像的正中间,(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2
注意,右下角的像素没有更改为2,因为它不是在上下左右四个方向上与初始点相连的像素点。
  • 注意:
1
2
3
image 和 image[0] 的长度在范围 [1, 50] 内。
给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 思路:广度优先搜索 / 深度优先搜索
// 我们从给定的起点开始,进行深度优先搜索。每次搜索到一个方格时,如果其与初始位置的方格颜色相同,就将该方格的颜色更新,以防止重复搜索;如果不相同,则进行回溯。
// 注意:因为初始位置的颜色会被修改,所以我们需要保存初始位置的颜色,以便于之后的更新操作。

// 碎碎念:题目读的怀疑人生。。。

const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
int n, m;
void dfs(int** image, int x, int y, int color, int newColor) {
if (image[x][y] == color) {
image[x][y] = newColor;
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < m) {
dfs(image, mx, my, color, newColor);
}
}
}
}
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) {
n = imageSize, m = imageColSize[0];
*returnSize = n;
for (int i = 0; i < n; i++) {
(*returnColumnSizes)[i] = m;
}
int currColor = image[sr][sc];
if (currColor != newColor) {
dfs(image, sr, sc, currColor, newColor);
}
return image;
}

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0

  1. 示例 1:

    demo

    1
    2
    3
    输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
    输出:6
    解释:答案不应该是 11 ,因为岛屿只能包含水平或垂直这四个方向上的 1
  2. 示例 2:

    1
    2
    输入:grid = [[0,0,0,0,0,0,0,0]]
    输出:0
  • 提示:

    1
    2
    3
    4
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 50
    grid[i][j] 为 01

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 思路:深度优先搜索

var maxAreaOfIsland = function(grid) {
const row = grid.length, col = grid[0].length
let res = 0
const DFS = (i, j) => {
// 下标越界返回0
if (i < 0 || i >= row || j < 0 || j >= col) {
return 0
}
// 值为0返回0
if(grid[i][j] == 0) {return 0}
// 访问过后置为0,防止重复访问
grid[i][j] = 0
// 递归计算岛屿面积
return 1 + DFS(i, j-1) + DFS(i-1, j) + DFS(i, j+1) + DFS(i+1, j)
}
// 遍历二维数组
for(let i=0; i<row; i++) {
for(let j=0; j<col; j++) {
if (grid[i][j] == 1) {
res = Math.max(res, DFS(i,j))
} else {
continue
}
}
}
return res
};