101 孤岛的总面积题目链接添加链接描述思路将每个岛的最外沿先都变成陆地再遍历即可文章详解·添加链接描述#includeiostream#includevectorusingnamespacestd;intdir[4][2]{-1,0,0,-1,1,0,0,1};// 保存四个方向voiddfs(vectorvectorintgrid,intx,inty){grid[x][y]0;for(inti0;i4;i){intnext_xxdir[i];intnext_yydir[i];if(next_x0next_xgrid.size()next_y0next_ygrid[0].size()){if(grid[next_x][next_y]1){dfs(grid,next_x,next_y);}}}}intmain(){intn,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}for(inti0;in;i){if(grid[i][0]1){dfs(grid,0,i);}if(grid[i][m-1]1){dfs(grid,m-1,i);}}for(intj0;jm;j){if(grid[0][j]1){dfs(grid,j,0);}if(grid[n-1][j]1){dfs(grid,j,n-1);}}intcount0;for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]1)count;}}coutcountendl;}102 沉没孤岛题目链接添加链接描述思路和上题类似将输入复制一份先遍历靠边的海岸根据第一幅图找到的孤岛在第二幅图中沉没即可文章详解添加链接描述#includeiostream#includevectorusingnamespacestd;intdir[4][2]{-1,0,0,-1,1,0,0,1};// 保存四个方向voiddfs(vectorvectorintgrid,intx,inty){grid[x][y]0;for(inti0;i4;i){intnext_xxdir[i][0];intnext_yydir[i][1];if(next_x0next_xgrid.size()next_y0next_ygrid[0].size()){if(grid[next_x][next_y]1){dfs(grid,next_x,next_y);}}}}intmain(){intn,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));vectorvectorintgrid_copy(n,vectorint(m,0));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];grid_copy[i][j]grid[i][j];}}for(inti0;in;i){if(grid[i][0]1){dfs(grid,i,0);}if(grid[i][m-1]1){dfs(grid,i,m-1);}}for(intj0;jm;j){if(grid[0][j]1){dfs(grid,0,j);}if(grid[n-1][j]1){dfs(grid,n-1,j);}}for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]1){grid_copy[i][j]0;}coutgrid_copy[i][j] ;}coutendl;}}103 水流问题题目链接添加链接描述思路从边界出发逆流而上第一组边界和第二组边界都标记的点就是结果集中的一个。文章详解添加链接描述#includeiostream#includevectorusingnamespacestd;intn,m;intdir[4][2]{-1,0,0,-1,1,0,0,1};voiddfs(vectorvectorintgrid,vectorvectorboolvisited,intx,inty){if(visited[x][y])return;visited[x][y]true;for(inti0;i4;i){intnextxxdir[i][0];intnextyydir[i][1];if(nextx0||nextxn||nexty0||nextym)continue;if(grid[x][y]grid[nextx][nexty])continue;// 注意这里是从低向高遍历dfs(grid,visited,nextx,nexty);}return;}intmain(){cinnm;vectorvectorintgrid(n,vectorint(m,0));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}// 标记从第一组边界上的节点出发可以遍历的节点vectorvectorboolfirstBorder(n,vectorbool(m,false));// 标记从第一组边界上的节点出发可以遍历的节点vectorvectorboolsecondBorder(n,vectorbool(m,false));// 从最上和最下行的节点出发向高处遍历for(inti0;in;i){dfs(grid,firstBorder,i,0);// 遍历最左列接触第一组边界dfs(grid,secondBorder,i,m-1);// 遍历最右列接触第二组边界}// 从最左和最右列的节点出发向高处遍历for(intj0;jm;j){dfs(grid,firstBorder,0,j);// 遍历最上行接触第一组边界dfs(grid,secondBorder,n-1,j);// 遍历最下行接触第二组边界}for(inti0;in;i){for(intj0;jm;j){// 如果这个节点从第一组边界和第二组边界出发都遍历过就是结果if(firstBorder[i][j]secondBorder[i][j])couti jendl;;}}}104 建造最大岛屿题目链接添加链接描述思路第一次遍历记录信息第二次遍历所有海洋格子计算相邻陆地面积。精妙之处在于如何确认相邻陆地属于哪一块陆地不好记录整体位置信息不妨化整为零我不记录你你向我报告你属于哪一块地。文章详解添加链接描述#includeiostream#includevector#includeunordered_set#includeunordered_mapusingnamespacestd;intn,m;intcount;intdir[4][2]{0,1,1,0,-1,0,0,-1};// 四个方向voiddfs(vectorvectorintgrid,vectorvectorboolvisited,intx,inty,intmark){if(visited[x][y]||grid[x][y]0)return;// 终止条件访问过的节点 或者 遇到海水visited[x][y]true;// 标记访问过grid[x][y]mark;// 给陆地标记新标签,化整为零count;for(inti0;i4;i){intnextxxdir[i][0];intnextyydir[i][1];if(nextx0||nextxn||nexty0||nextym)continue;// 越界了直接跳过dfs(grid,visited,nextx,nexty,mark);}}intmain(){cinnm;vectorvectorintgrid(n,vectorint(m,0));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}vectorvectorboolvisited(n,vectorbool(m,false));// 标记访问过的点unordered_mapint,intgridNum;intmark2;// 记录每个岛屿的编号boolisAllGridtrue;// 标记是否整个地图都是陆地for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]0)isAllGridfalse;if(!visited[i][j]grid[i][j]1){count0;dfs(grid,visited,i,j,mark);// 将与其链接的陆地都标记上 truegridNum[mark]count;// 记录每一个岛屿的面积mark;// 记录下一个岛屿编号}}}if(isAllGrid){coutn*mendl;// 如果都是陆地返回全面积return0;// 结束程序}// 以下逻辑是根据添加陆地的位置计算周边岛屿面积之和intresult0;// 记录最后结果unordered_setintvisitedGrid;// 标记访问过的岛屿for(inti0;in;i){for(intj0;jm;j){count1;// 记录连接之后的岛屿数量visitedGrid.clear();// 每次使用时清空if(grid[i][j]0){for(intk0;k4;k){intneariidir[k][1];// 计算相邻坐标intnearjjdir[k][0];if(neari0||nearin||nearj0||nearjm)continue;if(visitedGrid.count(grid[neari][nearj]))continue;// 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来countgridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]);// 标记该岛屿已经添加过}}resultmax(result,count);}}coutresultendl;}