岛屿问题初探（DFS）

0412 算法题第一题 查找1.1 题目1.2 思路这道题要从编号1开始查询数字然后输出这个数字第一次出现的编号若为查找到返回-1为了降低其时间复杂度我们可以采用二分法进行查找因为要找到其第一次出现的编号所以我们优先以收缩其右边界的结果为最终答案。这里注意以下标对应的数字作为左右端点这样确保每个数字都是要查找的数字即结果是有效的。while循环结束后验证一下结果。若等于输出对应ans若不等于输出-1。1.3 完整代码#includebits/stdc.husingnamespacestd;intmain(){intn,m;cinnm;vectorinta(n);intmid,ans1,q;for(inti0;in;i){cina[i];}for(inti0;im;i){cinq;intleft0,rightn-1;while(leftright){mid(leftright)/2;if(a[mid]q){ansmid1;rightmid-1;}else{leftmid1;}}if(a[ans-1]!q){cout-1 ;}else{coutans ;}}return0;}第二题 孤岛计数2.1 题目2.2 思路这道题我们要寻找孤岛即他的上下左右都是水我们先定义一个dfs函数即当我们找到了一个未被访问过的孤岛时我们要使用DFS函数去标记它周围的陆地并对该陆地进行dfs搜索保证该岛屿被标记彻底。这个函数是没有return语句的当周围为水域或该岛屿已被标记过时他会自动一层一层结束for循环注意剪枝优化若超出当前研究的范围直接进行跳过当前循环进入下一次深搜在主函数中我们先将所有孤岛标记为未访问过然后开始遍历所有岛屿。如果他是陆地且未被访问过我们就将岛屿该岛屿标记为已访问并将岛屿数量加一然后调用深搜函数将其周围相邻的陆地标记为已访问过。2.3 完整代码#includeiostream#includevectorusingnamespacestd;intdir[4][2]{0,1,1,0,-1,0,0,-1};voiddfs(constvectorvectorintgrid,vectorvectorboolvisited,intx,inty){for(inti0;i4;i){intnextxxdir[i][0];intnextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size())continue;if(!visited[nextx][nexty]grid[nextx][nexty]1){visited[nextx][nexty]true;dfs(grid,visited,nextx,nexty);}}}intmain(){intn,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}vectorvectorboolvisited(n,vectorbool(m,false));intresult0;for(inti0;in;i){for(intj0;jm;j){if(!visited[i][j]grid[i][j]1){visited[i][j]true;result;dfs(grid,visited,i,j);}}}coutresultendl;}