代码随想录训练营day51|图论part2

岛屿数量

卡码网题目链接

#include <bits/stdc++.h>
using namespace std;int dir[4][2] = {0,-1,0,1,1,0,-1,0};void dfs(vector<vector<int>> &board, vector<vector<bool>> &visted, int x, int y){for(int i = 0; i < 4; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if(nx >= board.size() || nx < 0 || ny >= board[0].size() || ny < 0 || board[nx][ny] == 0 || visted[nx][ny])continue;// board[nx][ny] = 0;visted[nx][ny] = true;dfs(board, visted, nx, ny);}
}void bfs(vector<vector<int>> &board, vector<vector<bool>> &visted, int x, int y){queue<pair<int, int>> que;que.push({x, y});while(!que.empty()){pair<int, int> s = que.front();que.pop();for(int i = 0; i < 4; i++){int nx = s.first + dir[i][0];int ny = s.second + dir[i][1];if(nx >= board.size() || nx < 0 || ny >= board[0].size() || ny < 0 || board[nx][ny] == 0 || visted[nx][ny])continue;visted[nx][ny] = true;que.push({nx, ny});}}}int main()
{int n, m;cin >> n >> m;vector<vector<int>> board(n, vector<int>(m));vector<vector<bool>> visted(n, vector<bool>(m, false));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> board[i][j];}}int result = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(board[i][j] == 1 && !visted[i][j]){result++;visted[i][j] = true;// dfs(board, visted, i, j);bfs(board, visted, i, j);}}}cout << result << endl;
}

深搜

int dir[4][2] = {0,-1,0,1,1,0,-1,0};
void dfs(vector<vector<int>> &board, vector<vector<bool>> &visted, int x, int y){for(int i = 0; i < 4; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if(nx >= board.size() || nx < 0 || ny >= board[0].size() || ny < 0 || board[nx][ny] == 0 || visted[nx][ny])continue;// board[nx][ny] = 0;visted[nx][ny] = true;dfs(board, visted, nx, ny);}
}

广搜

int dir[4][2] = {0,-1,0,1,1,0,-1,0};
void bfs(vector<vector<int>> &board, vector<vector<bool>> &visted, int x, int y){queue<pair<int, int>> que;que.push({x, y});while(!que.empty()){pair<int, int> s = que.front();que.pop();for(int i = 0; i < 4; i++){int nx = s.first + dir[i][0];int ny = s.second + dir[i][1];if(nx >= board.size() || nx < 0 || ny >= board[0].size() || ny < 0 || board[nx][ny] == 0 || visted[nx][ny])continue;visted[nx][ny] = true;que.push({nx, ny});}}
}

岛屿的最大面积

卡码网题目链接（ACM模式）

#include <bits/stdc++.h>
using namespace std;int result;
int dir[4][2] = {0,-1,0,1,1,0,-1,0};
void bfs(vector<vector<int>> &board, vector<vector<bool>> &visted, int x, int y){queue<pair<int, int>> que;que.push({x, y});int sum = 1;while(!que.empty()){pair<int, int> s = que.front();que.pop();for(int i = 0; i < 4; i++){int nx = s.first + dir[i][0];int ny = s.second + dir[i][1];if(nx >= board.size() || nx < 0 || ny >= board[0].size() || ny < 0 || board[nx][ny] == 0 || visted[nx][ny])continue;sum++;visted[nx][ny] = true;que.push({nx, ny});}}result = max(sum, result);
}int main()
{int n, m;cin >> n >> m;vector<vector<int>> board(n, vector<int>(m));vector<vector<bool>> visted(n, vector<bool>(m, false));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> board[i][j];}}result = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(board[i][j] == 1 && !visted[i][j]){visted[i][j] = true;// result++;bfs(board, visted, i, j);}}}cout << result;
}