代码随想录算法训练营Day51

第十一章：图论part02

岛屿数量 深搜

注意深搜的两种写法，熟练掌握这两种写法 以及 知道区别在哪里，才算掌握的深搜。

代码随想录

#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<vector<bool>>& visited, int x, int y) { if (visited[x][y] || grid[x][y] == 0) return; visited[x][y] = true; for (int i = 0; i < 4; i++) { int nextx = x + dir[i][0]; int nexty = y + dir[i][1]; if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过 dfs(grid, visited, nextx, nexty); } } 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) { result++; dfs(grid, visited, i, j); } } } cout << result << endl; } 岛屿数量 广搜

注意广搜的两种写法，第一种写法为什么会超时， 如果自己做的录友，题目通过了，也要仔细看第一种写法的超时版本，弄清楚为什么会超时，因为你第一次 幸运 没那么想，第二次可就不一定了。

代码随想录

#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 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, 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++; // 遇到没访问过的陆地，+1 bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true } } } cout << result << endl; } 岛屿的最大面积

本题就是基础题了，做过上面的题目，本题很快。

代码随想录

#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) { if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水 visited[x][y] = true; // 标记访问过 count++; for (int i = 0; i < 4; i++) { int nextx = x + dir[i][0]; int nexty = y + dir[i][1]; if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过 dfs(grid, visited, nextx, nexty); } } 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 = 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; // 因为dfs处理当前节点，所以遇到陆地计数为0，进dfs之后在开始从1计数 dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true result = max(result, count); } } } cout << result << endl; }