完成日期：7月16日，7月18日
今日总结：
- pair:结构体，有first、second成员
- emplace:构造函数+插入；insert:插入对象(已经构造过的)
- DFS需要写一个函数来递归，或者使用栈
- BFS使用队列
733. 图像渲染
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
// 方法一：广度优先搜索遍历BFS
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 newColor) {
int currColor = image[sr][sc]; // 记录这个颜色
if(currColor==newColor) return image; // 如果要改变的颜色与本来一样，就不许要改变
int n = image.size(), m = image[0].size();
queue<pair<int, int>> que; // 队列，注意pair的使用
que.emplace(sr, sc); // 注意emplace的使用
image[sr][sc] = newColor;
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] = newColor;
}
}
}
return image;
}
};
// 方法二：深度优先搜索遍历DFS
// DFS需要写一个函数来递归
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 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<image.size() && my>=0 && my<image[0].size()){
dfs(image, mx, my, color, newColor);
}
}
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int currColor = image[sr][sc];
if(currColor != newColor){
dfs(image, sr, sc, currColor, newColor);
}
return image;
}
};
695. 岛屿的最大面积
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
// DFS
class Solution {
public:
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
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();
stackj.pop();
stacki.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;
for(int index=0; index<4; ++index){
int next_i = cur_i+dx[index], next_j = cur_j+dy[index];
stacki.push(next_i);
stackj.push(next_j);
}
}
ans = max(ans, cur);
}
}
return ans;
}
};
//BFS
class Solution {
public:
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
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]==0) continue;
++cur;
grid[cur_i][cur_j] = 0;
for(int index = 0; index<4; ++index){
int next_i = cur_i + dx[index], next_j=cur_j+dy[index];
queuej.push(next_j);
queuei.push(next_i);
}
}
ans = max(ans, cur);
}
}
return ans;
}
};
