1.岛屿数量（深搜）
1.1 题目
https://kamacoder.com/problempage.php?pid=1171
1.2 题解
#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;/*邻接矩阵写法*///四个方向
int direct[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 };void dfs(const vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y)
{//确定终止条件if (visited[x][y] == true || grid[x][y] == 0)return;//当前节点标记访问过visited[x][y] = true;//开始遍历四个方向for (int i = 0; i < 4; i++){int nextx = x + direct[i][0];int nexty = y + direct[i][1];//如果越界了，结束本次循环if (nextx < 0 || nextx >= grid[1].size() || nexty < 0 || nexty >= grid[0].size())continue;dfs(grid, visited, nextx, nexty);}
}int main()
{//矩阵行数int n;//矩阵列数int 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) {result++;dfs(grid, visited, i, j);}}}cout << result << endl;}2.岛屿数量（广搜）
2.1题目
https://kamacoder.com/problempage.php?pid=1171
2.2 题解
#include <iostream>
#include <vector>
#include <queue>
#include <list>
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 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;}}}
}
int main()
{int n;int 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) {result++;bfs(grid, visited, i, j);}}}cout << result << endl;
}3.岛屿的最大面积
3.1 题目
https://kamacoder.com/problempage.php?pid=1172
3.2 题解
#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;int dir[4][2] = { 0,1,1,0,-1,0,0,-1 };void dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int& result)
{//判断终止条件if (visited[x][y] || grid[x][y] == 0)return;visited[x][y] = true;result++;for (int i = 0; i < 4; i++){int curx = x + dir[i][0];int cury = y + dir[i][1];//越界结束本次循环if (curx < 0 || curx >= grid.size() || cury < 0 || cury >= grid[1].size())continue;dfs(grid, visited, curx, cury, result);}
}
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;int temp = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (!visited[i][j] && grid[i][j] == 1) {dfs(grid, visited, i, j, temp);result = max(result, temp);temp = 0;}}}cout << result << endl;
}
