C++算法之搜索算法一 深度优先搜索
**
搜索算法
**
深度优先搜索和广度优先搜索是两种最常见的优先搜索方法,它们被广泛地运用在图和树等结构中进行搜索。
题目1
给定一个二维的0-1矩阵,其中0表示 海洋,1表示陆地,单独的或相邻的陆地可以形成岛屿,每个格子只与其上下左右四个格子相邻,求最大的岛屿面积。
一般来说,深度优先搜索类型的题目可以分为主函数和辅函数,主函数用于遍历所有的搜索位置,判断是否可以开始搜索,如果可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。
//使用栈的写法
vector<int>direction{[-1,0,1,0,-1};//对于四个方向遍历,创建一个数组
int maxAreaOfIsland(vector<vector<int>>&grid){
int m=grid.size(),n=m?grid[0].size():0,local_area,area=0,x,y;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]){
local_area=1;
grid[i][j]=0;
stack<pair><int,int>island;
island.push({i,j});
while(!island.empty()){
auto [r,c]=island.top();
island.pop();
for(int k=0;k<4;++k){
x=r+direction[k],y=c+direction[k+1];
if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
grid[x][y]=0;
++local_area;
island.push({x,y});
}
}
}
area=max(area,local_area);
}
}
}
return area;
}
递归写法
边界判定一般有两种写法,一种是先判定是否越界,只有在合法的情况下才进行下一步搜索(即判断放在调用递归函数前);另一种不管三七二十一先进行下一步搜索,待下一步搜索开始时再判断是否合法(即判断放在辅函数第一行),这里展示两种写法:
vector<int>derection{-1,0,1,0,-1};
//主函数
int maxAreaOFIsland(vector<vector<int>>&grid)){
if(grid.empty()||grid[0].empty()) return 0;
int max_area=0;
for(int i=0;i<grid.size();i++)
{
for(int j=0;j<grid[0].size();++j){
if(grid[i][j]==1){
max_area=max(max_area,dfs(grid,i,j);
}
}
}
return max_area;
}
//辅函数
int dfs(vector<vector<int>>&grid,int r,int c){
if(grid[r][c]==0) return 0;
grid[r][c]=0;
int x,y,area=1;
for(int i=0;i<4;i++){
x=r+direction[i],y=c+direction[i+1];
if(x>0&&x<grid.size()&&y>=0&&y<grid[0].size()){
area+=dfs(grid,x,y);
}
}
return area;
}
第二种递归写法
//主函数
int maxAreaOFIsland(vector<vector<int>>&&grid){
if(grid.empty()||grid[0].empty()) return 0;
int max_area=0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
max_area=max(max_area,dfs(grid,i,j));
}
}
return max_arrea;
}
//辅函数
int dfs(vector<vector<int>>&grid,int r,int c){
if(r<0||r>=grid.size()||c<0||c>=grid[0].size()||grid[r][c]==0){
return 0;
}
grid[r][c]=0;
return 1+dfs(grid,r+1,c)+dfs(grid,r-1,c)+dfs(grid,r,c+1)+dfs(grid,r,c-1);
}
题目二
给定一个二维的 0-1 矩阵,如果第 (i, j) 位置是 1,则表示第 i 个人和第 j 个人是朋友。已知
朋友关系是可以传递的,即如果 a 是 b 的朋友,b 是 c 的朋友,那么 a 和 c 也是朋友,换言之这
三个人处于同一个朋友圈之内。求一共有多少个朋友圈。
//主函数
int findCircleNum(vector<vector<int>>&friends){
int n=friends.size(),count=0;
vector<bool>visited(n,false);
for(int i=0;i<n;i++){
if(!visited[i]){
dfs(friend,i,visited);
++count;
}
}
return count;
}
//辅函数
void dfs(vector<vector<int>>&&friends,int i,vector<bool>&visited){
visited[i]=true;
for(int k=0;k<friends.size();k++){
if(friends[i][k]==1&&!visited[k]){
dfs(friends,k,visited);
}
}
}
题目3
给定一个二维的非负整数矩阵,每个位置的值表示海拔高度。假设左边和上边是太平洋,右
边和下边是大西洋,求从哪些位置向下流水,可以流到太平洋和大西洋。水只能从海拔高的位置
流到海拔低或相同的位置。
虽然题目要求的是满足向下流能到达两个大洋的位置,如果我们对所有的位置进行搜索,那么在不剪枝的情况下复杂度会很高。因此我们可以反过来想,从两个大洋开始向上流,这样我们只需要对矩形四条边进行搜索。搜索完成后,只需遍历一遍矩阵,满足条件的位置即为两个大洋向上流都能到达的位置。
vector<int>direction{-1,0,1,0,-1};
//主函数
vector<vector<int>>pacificAtlantic(vector<vector<int>>&matrix){
if(matrix.empty()||matrix[0].enmpty()){
return {};
}
vector<vector<int>>ans;
int m=matrix.size(),n=matrix[0].size()
vector<vector<bool>>can_reach_p(m,vector<bool>(n,false));
vector<vector<bool>>can_reach_a(m,vector<bool>(n,false));
for(int i=0;i<m;i++){
dfs(matrix,can_reach_p,i,0);
dfs(matrix,can_reach_a,i,n-1);
}
for(int i=0;i<n;i++){
dfs(matrix,can_reach_p,0,i);
dfs(matrix,can_reach_a,m-1,i);
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(can_reach_p[i][j]&&can_reach_a[i][j]){
ans.push_back(vector<int>{i,j});
}
}
}
return ans;
}
//辅函数
void dfs(const vector<vector<int>>&matrix,vector<vector<bool>>&can_reach,int r,int c){
if(can_reach[r][c]){
return;
}
can_reach[r][c]==true;
int x,y;
for(int i=0;i<4;i++){
x=r+direction[i],y=c+direction[i+1];
if(x>=0&&x<matrix.size()&&y>=0&&y<matrix[0].size()&&matrix[r][c]<=matrix[x][y]){
dfs(matrix,can_reach,x,y);
}
}
}
this section is a little to learn,so you have to trying!
相关文章
- 刷题、找工作,学C++不会STL怎么行?vector篇(下)
- c++语言截取字符串,详解C++ string常用截取字符串方法
- c++获取子类窗口句柄位置_C++中各种获取窗口句柄的方法「建议收藏」
- 深入理解C++11_c++ string char
- C++构造函数的作用_c++什么是构造函数
- C++字符串的奇技淫巧
- C++从入门到精通(第十篇) :二叉搜索树
- c++读写文件的几种方法_include有什么用
- C++ 不知树系列之二叉排序树(递归和非递归遍历、删除、插入……)
- C++ 不知图系列之基于邻接矩阵实现广度、深度搜索
- c++的链表-C++链表
- C/C++ 搜索缝隙并插入ShellCode
- 【C++】二叉搜索树
- 【C++】map 和 set
- 【C++】继承
- c++基础篇之C++ 模板
- Python 调用 C++详解编程语言
- C++管理输出缓冲区
- C++实现二叉树非递归遍历方法实例总结
- C++编译器无法捕捉到的8种错误实例分析
- 贪吃蛇游戏C++命令行版实例代码