代码随想录60期day54

岛屿dfs

#include<iostream>
#include<vector>
using namespace std;int dir[4][2] = {0,1,1,0,-1,0,0,-1};void dfs(const vector<vector<int>>&grid,vector<vecotr<bool>>&visited,int x,int y){for(int i = 0 ; i < 4; i++){int newtx = x + dir[i][0];int newty = y + dir[i][0];if(newtx < 0 || newtx > grid.size() || newty < 0 || newty >= grid[0].size()) continue;if(!visited[newtx][newty] && grid[newtx][newty] == 1){visited[newtx][newty] = true;dfs(grid,visited,newtx,newty);}}
}int main(){int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,n));for(int i = 0 ; i <n;i++){for(int j = 0;j <m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(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){visited[i][j] = true;result++;dfs(grid,visited,i,j);}}}cout<<result<<endl;
}

岛屿bfs

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int dir[4][2] = {0,1,1,0,-1,0,0,-1};void bfs(const vector<vector<int>>&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 newtx = curx + dir[i][0];int newty = cury + dir[i][1];if(newtx < 0 || newtx >= grid.size() || newty < 0 || newty >= grid[0].size()){que.push({newtx,newty});visited[newtx][newty] = true;}}}
}int main(){int n,m;cin>>n>>m;vector<vecotr<int>>grid(n,vector<int>(m,0));for(int i = 0; i<n;i++){for(int j = 0;j<m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(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++;bfs(grid,visited,i,j);}}}cout<<result<<endl;
}

100. 岛屿的最大面积

dfs

#include<iostream>
#include<vector>
using namespace std;
int count;
int dir[4][2] = {0,1,1,0,-1,0,0,-1};void dfs(vector<vector<int>>&grid,vector<vector<bool>>&visited,int x,int y){for(int i = 0;i<4;i++){int newtx = x + dir[i][0];int newty = y + dir[i][1];if(newtx < 0 || newtx >=grid.size() || newty < 0 || newty >= grid[0].size()) continue;if(!visited[newtx][newty] && grid[newtx][newty] == 1){visited[newtx][newty] = true;count++;dfs(grid,visited,newtx,newty)}}
}int main(){int n,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(int i = 0 ; i <n;i++){for(int j = 0;j<m;j++){cin>>grid[i][j];}}vector<vector<bool>>visited(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){count++;visited[i] = true;dfs(grid,visited,i,j);result = max(result,count);}}}cout<<result<<endl;
}

bfs

class Solution {
private:int count;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<int> que;que.push(x);que.push(y);visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点count++;while(!que.empty()) {int xx = que.front();que.pop();int yy = que.front();que.pop();for (int i = 0 ;i < 4; i++) {int nextx = xx + dir[i][0];int nexty = yy + 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;count++;que.push(nextx);que.push(nexty);}}}}public:int maxAreaOfIsland(vector<vector<int>>& 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) {count = 0;bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 trueresult = max(result, count);}}}return result;}
};