一，图像渲染
733. 图像渲染 - 力扣（LeetCode）
https://leetcode.cn/problems/flood-fill/?plan=algorithms&plan_progress=gzwnnxs
本题要求将给定的二维数组中指定的「色块」染成另一种颜色。「色块」的定义是：直接或间接相邻的同色方格构成的整体。
可以发现，「色块」就是被不同颜色的方格包围的一个同色岛屿。我们从色块中任意一个地方开始，利用广度优先搜索或深度优先搜索即可遍历整个岛屿。
注意：当目标颜色和初始颜色相同时，我们无需对原数组进行修改。
1，广度优先搜索
思路及算法
我们从给定的起点开始，进行广度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。
注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
class Solution { public: const int dx[4] = {1, 0, 0, -1}; const int dy[4] = {0, 1, -1, 0}; vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int currColor = image[sr][sc]; if (currColor == color) { return image; } int n = image.size(), m = image[0].size(); queue<pair<int, int>> que; que.emplace(sr, sc); image[sr][sc] = color; while (!que.empty()) { int x = que.front().first, y = que.front().second; que.pop(); 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 && image[mx][my] == currColor) { que.emplace(mx, my); image[mx][my] = color; } } } return image; } };
复杂度分析
时间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
空间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。主要为队列的开销。
2，深度优先搜索
思路及算法
我们从给定的起点开始，进行深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。
注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
class Solution { public: const int dx[4] = {1, 0, 0, -1}; const int dy[4] = {0, 1, -1, 0}; void dfs(vector<vector<int>>& image, int x, int y, int currColor, int color) { if (image[x][y] == currColor) { image[x][y] = color; for (int i = 0; i < 4; i++) { int mx = x + dx[i], my = y + dy[i]; if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size()) { dfs(image, mx, my, currColor, color); } } } } vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int currColor = image[sr][sc]; if (currColor != color) { dfs(image, sr, sc, currColor, color); } return image; } };
复杂度分析
时间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
空间复杂度：O(n×m)，其中 n和 m 分别是二维数组的行数和列数。主要为栈空间的开销。
二，岛屿的最大面积
695. 岛屿的最大面积 - 力扣（LeetCode）
https://leetcode.cn/problems/max-area-of-island/?plan=algorithms&plan_progress=gzwnnxs
1，深度优先搜索
我们想知道网格中每个连通形状的面积，然后取最大值。
如果我们在一个土地上，以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。
为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0。这样我们就不会多次访问同一土地。
class Solution { int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) { if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) { return 0; } grid[cur_i][cur_j] = 0; int di[4] = {0, 0, 1, -1}; int dj[4] = {1, -1, 0, 0}; int ans = 1; for (int index = 0; index != 4; ++index) { int next_i = cur_i + di[index], next_j = cur_j + dj[index]; ans += dfs(grid, next_i, next_j); } return ans; } public: int maxAreaOfIsland(vector<vector<int>>& grid) { int ans = 0; for (int i = 0; i != grid.size(); ++i) { for (int j = 0; j != grid[0].size(); ++j) { ans = max(ans, dfs(grid, i, j)); } } return ans; } };
复杂度分析
时间复杂度：O(m×n)。其中 mm 是给定网格中的行数，n 是列数。我们访问每个网格最多一次。
空间复杂度：O(m×n)，递归的深度最大可能是整个网格的大小，因此最大可能使用 O(m×n) 的栈空间。
2，深度优先搜索 + 栈
算法
我们可以用栈来实现深度优先搜索算法。这种方法本质与方法一相同，唯一的区别是：
方法一通过函数的调用来表示接下来想要遍历哪些土地，让下一层函数来访问这些土地。而方法二把接下来想要遍历的土地放在栈里，然后在取出这些土地的时候访问它们。
访问每一片土地时，我们将对围绕它四个方向进行探索，找到还未访问的土地，加入到栈stack 中；
另外，只要栈stack 不为空，就说明我们还有土地待访问，那么就从栈中取出一个元素并访问。
class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { int ans = 0; for (int i = 0; i != grid.size(); ++i) { for (int j = 0; j != grid[0].size(); ++j) { int cur = 0; stack<int> stacki; stack<int> stackj; stacki.push(i); stackj.push(j); while (!stacki.empty()) { int cur_i = stacki.top(), cur_j = stackj.top(); stacki.pop(); stackj.pop(); if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) { continue; } ++cur; grid[cur_i][cur_j] = 0; int di[4] = {0, 0, 1, -1}; int dj[4] = {1, -1, 0, 0}; for (int index = 0; index != 4; ++index) { int next_i = cur_i + di[index], next_j = cur_j + dj[index]; stacki.push(next_i); stackj.push(next_j); } } ans = max(ans, cur); } } return ans; } };
复杂度分析
时间复杂度：O(m×n)。其中 m 是给定网格中的行数，n 是列数。我们访问每个网格最多一次。
空间复杂度：O(m×n)，栈中最多会存放所有的土地，土地的数量最多为 m×n 块，因此使用的空间为 O(m×n)。
3，广度优先搜索
算法
我们把方法二中的栈改为队列，每次从队首取出土地，并将接下来想要遍历的土地放在队尾，就实现了广度优先搜索算法。
class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { int ans = 0; for (int i = 0; i != grid.size(); ++i) { for (int j = 0; j != grid[0].size(); ++j) { int cur = 0; queue<int> queuei; queue<int> queuej; queuei.push(i); queuej.push(j); while (!queuei.empty()) { int cur_i = queuei.front(), cur_j = queuej.front(); queuei.pop(); queuej.pop(); if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) { continue; } ++cur; grid[cur_i][cur_j] = 0; int di[4] = {0, 0, 1, -1}; int dj[4] = {1, -1, 0, 0}; for (int index = 0; index != 4; ++index) { int next_i = cur_i + di[index], next_j = cur_j + dj[index]; queuei.push(next_i); queuej.push(next_j); } } ans = max(ans, cur); } } return ans; } };
复杂度分析
时间复杂度：O(m×n)。其中 m 是给定网格中的行数，n 是列数。我们访问每个网格最多一次。
空间复杂度：O(m×n)，队列中最多会存放所有的土地，土地的数量最多为 m×n 块，因此使用的空间为 O(m×n)。
