当前位置：首页 > news >正文

岛屿问题初探（DFS）

news 2026/4/14 20:42:03

0412 算法题

第一题查找

1.1 题目

1.2 思路

这道题要从编号1开始查询数字，然后输出这个数字第一次出现的编号；若为查找到，返回-1；
为了降低其时间复杂度，我们可以采用二分法进行查找，因为要找到其第一次出现的编号，所以我们优先以收缩其右边界的结果为最终答案。
这里注意以下标对应的数字作为左右端点，这样确保每个数字都是要查找的数字，即结果是有效的。
while循环结束后，验证一下结果。若等于，输出对应ans；若不等于，输出-1。

1.3 完整代码

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,m;cin>>n>>m;vector<int>a(n);intmid,ans=1,q;for(inti=0;i<n;i++){cin>>a[i];}for(inti=0;i<m;i++){cin>>q;intleft=0,right=n-1;while(left<=right){mid=(left+right)/2;if(a[mid]>=q){ans=mid+1;right=mid-1;}else{left=mid+1;}}if(a[ans-1]!=q){cout<<"-1 ";}else{cout<<ans<<" ";}}return0;}

第二题孤岛计数

2.1 题目

2.2 思路

这道题，我们要寻找孤岛，即他的上下左右都是水；我们先定义一个dfs函数，即当我们找到了一个未被访问过的孤岛时，我们要使用DFS函数去标记它周围的陆地，并对该陆地进行dfs搜索，保证该岛屿被标记彻底。（这个函数是没有return语句的，当周围为水域或该岛屿已被标记过时，他会自动一层一层结束for循环）（注意剪枝优化，若超出当前研究的范围，直接进行跳过当前循环，进入下一次深搜）
在主函数中，我们先将所有孤岛标记为未访问过，然后开始遍历所有岛屿。如果他是陆地且未被访问过，我们就将岛屿该岛屿标记为已访问；并将岛屿数量加一，然后调用深搜函数，将其周围相邻的陆地标记为已访问过。

2.3 完整代码

#include<iostream>#include<vector>usingnamespacestd;intdir[4][2]={0,1,1,0,-1,0,0,-1};voiddfs(constvector<vector<int>>&grid,vector<vector<bool>>&visited,intx,inty){for(inti=0;i<4;i++){intnextx=x+dir[i][0];intnexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){visited[nextx][nexty]=true;dfs(grid,visited,nextx,nexty);}}}intmain(){intn,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(n,vector<bool>(m,false));intresult=0;for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(!visited[i][j]&&grid[i][j]==1){visited[i][j]=true;result++;dfs(grid,visited,i,j);}}}cout<<result<<endl;}