算法训练营day65-岛屿连同问题

深搜-岛屿：99. 岛屿数量 (kamacoder.com)

// 深度搜索 dfs
#include<bits/stdc++.h>using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};void dfs(vector<vector<int>>& map, vector<vector<bool>>& findednode, int newx, int newy) {if(map[newx][newy] == 0 || findednode[newx][newy] == true) return;findednode[newx][newy] = true;for(int i = 0;i < 4;i++) {int nextx = newx + dir[i][0];int nexty = newy + dir[i][1];if(nextx < 0 || nextx >= map.size() || nexty < 0 || nexty >= map[0].size()) continue;dfs(map, findednode, nextx, nexty);}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> map(n, vector<int>(m));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {cin >> map[i][j];}}int result = 0;vector<vector<bool>> findednode(n, vector<bool>(m, false));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {if(map[i][j] == 1 && findednode[i][j] == false) {result++;dfs(map, findednode, i, j);}}}cout << result << endl;return 0;
}

// 深度搜索 dfs 递归终止条件写在for里面了
#include<bits/stdc++.h>using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};void dfs(vector<vector<int>>& map, vector<vector<bool>>& findednode, int newx, int newy) {findednode[newx][newy] = true;for(int i = 0;i < 4;i++) {int nextx = newx + dir[i][0];int nexty = newy + dir[i][1];if(nextx < 0 || nextx >= map.size() || nexty < 0 || nexty >= map[0].size()) continue;if(findednode[nextx][nexty] != true && map[nextx][nexty] == 1) {dfs(map, findednode, nextx, nexty);}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> map(n, vector<int>(m));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {cin >> map[i][j];}}int result = 0;vector<vector<bool>> findednode(n, vector<bool>(m, false));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {if(map[i][j] == 1 && findednode[i][j] == false) {result++;dfs(map, findednode, i, j);}}}cout << result << endl;return 0;
}

广搜-岛屿：99. 岛屿数量 (kamacoder.com)

// 深度搜索 dfs
#include<bits/stdc++.h>using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};void bfs(vector<vector<int>>& map, vector<vector<bool>>& findednode, int newx, int newy) {queue<pair<int, int>> qu;qu.push(pair<int,int>(newx, newy));findednode[newx][newy] = true;while(!qu.empty()) {pair<int, int>cur = qu.front();qu.pop();int x = cur.first;int y = cur.second;for(int i = 0;i < 4;i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx >= map.size() || nexty < 0 || nexty >= map[0].size()) continue;if(findednode[nextx][nexty] != true && map[nextx][nexty] == 1) {qu.push(pair<int, int>(nextx, nexty));findednode[nextx][nexty] = true;}}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> map(n, vector<int>(m));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {cin >> map[i][j];}}int result = 0;vector<vector<bool>> findednode(n, vector<bool>(m, false));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {if(map[i][j] == 1 && findednode[i][j] == false) {result++;bfs(map, findednode, i, j);}}}cout << result << endl;return 0;
}

题目：100. 岛屿的最大面积 (kamacoder.com)

#include<bits/stdc++.h>using namespace std;
int size = 0;
int dir[4][2] = {0,-1,-1,0,0,1,1,0};void bfs(vector<vector<int>>& map, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> qu;qu.push(pair<int, int>(x, y));visited[x][y] = true;while(!qu.empty()) {size++;pair<int, int> cur = qu.front();qu.pop();int newx = cur.first;int newy = cur.second;for(int i = 0;i < 4;i++) {int nextx = newx + dir[i][0];int nexty = newy + dir[i][1];if(nextx < 0 || nextx >= map.size() || nexty < 0 || nexty >= map[0].size()) continue;if(!visited[nextx][nexty] && map[nextx][nexty] == 1) {visited[nextx][nexty] = true;qu.push(pair<int, int>(nextx, nexty));}}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> map(n, vector<int>(m , 0));for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {cin >> map[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(map[i][j] == 1 && !visited[i][j]) {size = 0;bfs(map, visited, i, j);result = max(result, size);}}}cout << result << endl;return 0;
}