之前并查集也可以写问题 1问题2class Solution { public: // 深度优先搜索把与 (i, j) 相连的整座岛屿染成编号 id void dfs(vectorvectorint grid,int n,int m,int i,int j,int id){ // 越界 或 不是未访问的陆地(1) 就返回 if(i0 || i n || j0 || j m || grid[i][j] ! 1) return; grid[i][j] id; // 染色同时避免重复访问 dfs(grid,n,m,i-1,j,id); // 上 dfs(grid,n,m,i1,j,id); // 下 dfs(grid,n,m,i,j1,id); // 右 dfs(grid,n,m,i,j-1,id); // 左 } int largestIsland(vectorvectorint grid) { int n grid.size(); int m grid[0].size(); int id 2; // 岛屿编号从 2 开始0 是海1 是未染色陆地 // 1. 给每座岛屿染色编号依次为 2, 3, 4, ... for(int i 0;in;i){ for(int j 0;jm;j){ if(grid[i][j] 1) dfs(grid,n,m,i,j,id); } } // 2. 统计每座岛屿的面积sizes[k] 表示编号为 k 的岛屿面积 int ans 0; vectorint sizes(id,0); for(int i 0 ;in;i){ for(int j 0;jm;j){ if(grid[i][j]1) ans max(ans,sizes[grid[i][j]]); } } // 3. 枚举每个 0 格子尝试把它变成 1合并上下左右不同的岛屿 vectorbool visited(id); // 标记本轮已经合并过的岛屿编号防止重复加 int up,down,left,right,merge; for(int i 0;in;i){ for(int j 0;jm;j){ if(grid[i][j] 0){ // 取四个方向的格子编号越界或海则记为 0 up i0 ? grid[i-1][j] : 0; down i1n ? grid[i1][j] : 0; left j0 ? grid[i][j-1] : 0; right j1m ? grid[i][j1] : 0; // 当前 0 变成 1 后面积至少为 1 visited[up] true; merge sizes[up] 1; // 下面三个方向只有没被本轮合并过才加面积 if(!visited[down]){ merge sizes[down]; visited[down] true; } if(!visited[left]){ merge sizes[left]; visited[left] true; } if(!visited[right]){ merge sizes[right]; visited[right] true; } ans max(ans,merge); // 更新答案 // 还原 visited供下一个 0 格子使用 visited[up] false; visited[down] false; visited[left] false; visited[right] false; } } } return ans; } };问题3class Solution { public: int n, m; // 行数、列数 vectorvectorint grid; // 成员变量方便 dfs / worth 直接访问 // 从 (i,j) 出发把与它相连的、值为 1 的砖块全部标记为 2稳定砖块 // 返回本次 dfs 访问到的砖块数量 int dfs(int i, int j){ // 越界 或 不是值为 1 的砖块直接返回 0 if(i0 || in || j0 || jm || grid[i][j] ! 1) return 0; grid[i][j] 2; // 标记为“稳定/已访问” // 当前这块 上下左右四个方向递归 return 1 dfs(i1,j) dfs(i-1,j) dfs(i,j1) dfs(i,j-1); } // 判断 (i,j) 这块砖是否“值得”做一次 dfs // 条件它是砖(值为1)并且能通过顶行或某个相邻稳定砖(值为2)与顶部连通 bool worth(int i,int j){ return grid[i][j] 1 ( i 0 // 在第一行直接连顶 || (i0 grid[i-1][j] 2) // 上方是稳定砖 || (i1n grid[i1][j] 2) // 下方是稳定砖 || (j0 grid[i][j-1] 2) // 左方是稳定砖 || (j1m grid[i][j1] 2)); // 右方是稳定砖 } vectorint hitBricks(vectorvectorint g, vectorvectorint h) { grid g; // 拷贝一份避免修改原矩阵 n g.size(); m g[0].size(); int h_size h.size(); vectorint ans(h_size); // 存储每次敲击后掉落的砖块数 // 只有一行时敲掉第一行任意砖都会导致该行砖掉落 // 这里直接返回全 0属于题目边界处理一行时无“上方连接”概念 if(n 1) return ans; // 第一步先把所有要敲的砖从 grid 中“敲掉”值减 11-0 for(auto hit : h){ grid[hit[0]][hit[1]]--; } // 第二步从顶行开始 dfs标记所有与顶部连通的稳定砖块为 2 for(int i 0;im;i){ dfs(0,i); } // 第三步逆序还原敲击判断每块恢复的砖是否会带来新的掉落 for(int i h_size-1,row,col;i0;i--){ row h[i][0]; col h[i][1]; grid[row][col]; // 把这块砖恢复0-1 if(worth(row,col)){ // 如果它能和顶部连通 ans[i] dfs(row,col)-1; // 新增的稳定砖数减去自己 } } return ans; } };以上思路和代码来自B站左程云