代码随想录（番外）图论2

4. 岛屿数量.深搜版
5. 岛屿数量.广搜版
6. 岛屿的最大面积

https://programmercarl.com/0200.%E5%B2%9B%E5%B1%BF%E6%95%B0%E9%87%8F.%E6%B7%B1%E6%90%9C%E7%89%88.html

4. 岛屿数量.深搜版

class Solution {
public:int dir[4][2]={0,1,1,0,-1,0,0,-1};//4个方向，每行代表一个方向，上右下左void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int x,int y)//如果搞不清可以画一个坐标轴{for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size()) continue;//超二维数组就判断出界，跳过if(!visited[nextx][nexty]&&grid[nextx][nexty]=='1')// 没有访问过的 同时 是陆地的{visited[nextx][nexty]=true;dfs(grid,visited,nextx,nexty);//通过dfs把所有链接的土地找到}}}int numIslands(vector<vector<char>>& grid) {int n=grid[0].size();int m=grid.size();int result=0;vector<vector<bool>> visited=vector<vector<bool>>(m,vector<bool>(n,false));for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(!visited[i][j]&&grid[i][j]=='1'){   result++; // 遇到没访问过的陆地，+1dfs(grid,visited,i,j); // 将与其链接的陆地都标记上 true}}return result;}
};

5. 岛屿数量.广搜版

class Solution {
private:
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que;que.push({x, y});visited[x][y] = true; // 只要加入队列，立刻标记while(!que.empty()) {pair<int ,int> cur = que.front(); que.pop();int curx = cur.first;int cury = cur.second;for (int i = 0; i < 4; i++) {int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {que.push({nextx, nexty});visited[nextx][nexty] = true; // 只要加入队列立刻标记}}}
}
public:int numIslands(vector<vector<char>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j] && grid[i][j] == '1') {result++; // 遇到没访问过的陆地，+1bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true}}}return result;}
};

6. 岛屿的最大面积

class Solution {
public:int count;int dir[4][2]={0,1,1,0,0,-1,-1,0};void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nexty<0||nextx>=grid.size()||nexty>=grid[0].size()) continue;if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){visited[nextx][nexty]=true;count++;dfs(grid,visited,nextx,nexty);}}}int maxAreaOfIsland(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();int result=0;vector<vector<bool>>visited=vector<vector<bool>>(m,vector<bool>(n,false));for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(!visited[i][j]&&grid[i][j]==1){count=1;visited[i][j]=true;dfs(grid,visited,i,j);result=max(result,count);}}return result;}
};

总结
其实就是dfs之后在遍历一个正常岛屿后比大小，里面的小错误差点把我整红温了，就是对nextx,nexty 的grid[0].size()，的[0]忘写了最后dbug成功，还有就是在类型里面多delete>，找了半天没找到，躺着打效率确实有点低。