这次先从一道经典题说起。先通过理解这道题的思路,体会BFS与DFS算法的思想后,再对BFS和DFS做进一步讨论。

图像渲染

题目

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

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

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

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

示例:

输入: 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]]

如果觉得题目不好理解,可以到原题的讨论区看一下:

思路分析

我们首先要得到这个图的边界,使用vector::size()即可:

1
2
3
4
int row=image.size();
int column=image[0].size();//这个比较妙,学一学
//int column=sizeof(image)/(sizeof(int)*row)
//这个low得一批👆

然后把image[sr][sc]改为新的数字。问题是我们要通过怎样的方式来访问和(sr,sc)颜色相同的所有点?

广度优先搜索

我们这里就这道题来梳理BFS的思路。

思路图解,引用自力扣

这里用到了队列的数据结构:首先要把(sr,sc)这个点入队。然后访问队首元素,如果它上下左右的点和它值相同,那么这个点也入队,最后队首元素出队;一直循环,直到队列为空

队列来表示 就是这样的:

按照这个思路,就可以写出下面的代码:

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
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int flag=image[sr][sc];
if(flag==newColor) return image;
image[sr][sc]=newColor;
int row=image.size(),column=image[0].size();
pair<int,int> dir[4]={{-1,0},{0,1},{1,0},{0,-1}};
queue<pair<int,int>> que;
que.emplace(sr,sc);
while(!que.empty()){
for(auto i:dir){
int r=que.front().first+i.second;
int c=que.front().second+i.first;
if(r<0||r>=row||c<0||c>=column) continue;
if(image[r][c]==flag){
que.emplace(r,c);
image[r][c]=newColor;
}
}
que.pop();
}
return image;
}
};

这里我用pair来表示坐标,pair::first就是横坐标,pair::second就是纵坐标;用pair<int,int>类型的数组来管理左、上、右、下四个方向。每次要访问一个点的这四个方向时,直接使用基于范围的for循环 即可。

judge

起伏还比较大,这里我选用比较平均的一个结果:

看来性能并不是特别好……

深度优先搜索

我们这里就这道题来梳理DFS的思路。

思路图解,自己仿照上面BFS的图用PPT做的

可以用栈的数据结构来表示:首先把(sr,sc)这个点入栈,然后依次访问其左、上、右、下四个点,如果它的值为1,那么这个点入栈;如果四个方向都访问了,那么这个点出栈。当栈为空的时候,结束。

队列来表示 就是这样的:

于是按照这个思路,可以写出下面的代码:

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
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int flag=image[sr][sc];
if(flag==newColor) return image;
image[sr][sc]=newColor;
int row=image.size(),column=image[0].size();
pair<int,int> dir[]={{-1,0},{0,1},{1,0},{0,-1}};
stack<pair<int,int>> stk;
stk.emplace(sr,sc);
while(!stk.empty()){
for(auto i:dir){
int r=stk.top().first+i.second;
int c=stk.top().second+i.first;
if(i.first==0 && i.second==-1) stk.pop();
if(r<0||r>=row||c<0||c>=column) continue;
if(image[r][c]==flag){
image[r][c]=newColor;
stk.emplace(r,c);
break;
}
}
}
return image;
}
};
judge

看起来比之前的做法并没有好到哪里去……

递归写法

众所周知,可以写成递归形式的程序,也可以用栈来写。实际上,DFS就可以写成递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
void DFS(vector<vector<int>>& image, int sr, int sc, int newColor){
int row=image.size(),column=image[0].size();
int flag=image[sr][sc];
image[sr][sc]=newColor;
pair<int,int> dir[]={{-1,0},{0,1},{1,0},{0,-1}};
for(auto i:dir){
int r=sr+i.second,c=sc+i.first;
if(r<0||r>=row||c<0||c>column) continue;
if(image[r][c]==flag) DFS(image,r,c,newColor);
}
}
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor){
if(image[sr][sc]!=newColor)
DFS(image,sr,sc,newColor);
return image;
}
};

感觉递归形式其实还更好理解,(也更好写,毕竟一遍过

judge

看来性能比非递归形式的要好一些……

我一般认为递归应该会慢一些来着,因为有函数调用的额外开销。但是这道题就有点反我的常理了,下次去问一下老师递归好还是非递归好。

BFS与DFS

至此,我们可以总结一下广度优先搜索(BFS)和深度优先搜索(DFS)算法了。

  1. 这两个算法都是图的算法,对于树就类似于层序遍历前中后三序遍历(当然也有区别,比如遍历和搜索不是一个概念。遍历可以看成所有点都满足条件的搜索 )。

  2. BFS用到了队列的数据结构,DFS用到了栈的数据结构,也可以写成递归的形式。

  3. 上面的题可以看成一个四叉树的模型,一个点的四个方向就是四个孩子,如果那个方向超过边缘了就相当于对应孩子为空。

岛屿的最大面积

题目

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

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

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

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

示例:


输入: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

思路

我们可以从上往下,从左往右遍历这张图。如果碰到了1,那么就进行广度优先/深度优先搜索,并且将统计了的1改为0,这样就不会在一块上遍历多次了。

广度优先搜索

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
33
34
class Solution {
public:
int getAreaofIsland(vector<vector<int>>& grid,pair<int,int> p){
int area=1,row=grid.size(),column=grid[0].size();
queue<pair<int,int> > que;
pair<int,int> dir[]={{-1,0},{0,1},{1,0},{0,-1}};
que.push(p);
grid[p.first][p.second]=0;
while(!que.empty()){
for(auto i:dir){
int r=que.front().first+i.second;
int c=que.front().second+i.first;
if(r<0||r>=row||c<0||c>=column) continue;
if(grid[r][c]!=0){
grid[r][c]=0;
que.emplace(r,c);
area++;
}
}
que.pop();
}
return area;
}
int maxAreaOfIsland(vector<vector<int> >& grid) {
int row=grid.size(),column=grid[0].size(),Max=0;;
for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
if(grid[i][j]==1)
Max=max(Max,getAreaofIsland(grid,{i,j}));
}
}
return Max;
}
};
judge

性能并不是很好……

深度优先搜索

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
33
class Solution {
public:
int getAreaofIsland(vector<vector<int>>& grid,pair<int,int> p){
int area=1,row=grid.size(),column=grid[0].size();
stack<pair<int,int>> stk;
pair<int,int> dir[]={{-1,0},{0,1},{1,0},{0,-1}};
stk.push(p);
grid[p.first][p.second]=0;
while(!stk.empty()){
for(auto i:dir){
int r=stk.top().first+i.second;
int c=stk.top().second+i.first;
if(i.first==0&&i.second==-1) stk.pop();
if(r<0||r>=row||c<0||c>=column) continue;
if(grid[r][c]==1){
grid[r][c]=0;
stk.push({r,c});
area++;
break;
}
}
}
return area;
}
int maxAreaOfIsland(vector<vector<int> >& grid) {
int row=grid.size(),column=grid[0].size(),Max=0;
for(int i=0;i<row;i++)
for(int j=0;j<column;j++)
if(grid[i][j]==1)
Max=max(Max,getAreaofIsland(grid,{i,j}));
return Max;
}
};
judge

和之前的解法依旧旗鼓相当……

DFS的递归形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int getAreaofIsland(vector<vector<int>>& grid,pair<int,int> p){
int area=1,row=grid.size(),column=grid[0].size();
grid[p.first][p.second]=0;
pair<int,int> dir[]={{-1,0},{0,1},{1,0},{0,-1}};
for(auto i:dir){
int r=p.first+i.second,c=p.second+i.first;
if(r<0||r>=row||c<0||c>=column) continue;
if(grid[r][c]==1)
area+=getAreaofIsland(grid,{r,c});
}
return area;
}
int maxAreaOfIsland(vector<vector<int> >& grid) {
int row=grid.size(),column=grid[0].size(),Max=0;;
for(int i=0;i<row;i++)
for(int j=0;j<column;j++)
if(grid[i][j]==1)
Max=max(Max,getAreaofIsland(grid,{i,j}));
return Max;
}
};
judge