代码随想录第五十七天

99.  岛屿数量 深搜

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

代码随想录

#include <iostream>
#include <vector>
using namespace std;int dir[4][2] = { 0, 1, 1, 0, -1, 0, 0, -1 }; // 四个方向
void dfs(vector<vector<int>>& grid, 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 < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size() || grid[nx][ny]==0) continue;grid[nx][ny] =0;dfs(grid,nx,ny);}
}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];}}int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {grid[i][j] =0;result++;dfs(grid, i, j);}}}cout << result << endl;
}

99.  岛屿数量 广搜

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

代码随想录

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {int x,y;node(int x, int y) :x(x), y(y) {};
};
queue<node>que;
int n, m;
int res = 0;
void bfs(vector<vector<int>>&mp,int x,int y) {que.push(node(x, y));int dx[] = { 0,0,-1,1 };int dy[] = { 1,-1,0,0 };while (!que.empty()) {node cur = que.front();que.pop();for (int i = 0; i < 4; i++) {int xx = cur.x + dx[i];int yy = cur.y + dy[i];if (xx<0 || xx>=mp.size() || yy<0 || yy>=mp[0].size() || mp[xx][yy] == 0)continue;mp[xx][yy] = 0;que.push(node(xx, yy));}}
}
void solve() {cin >> n >> m;//建图vector<vector<int>>mp(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> mp[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (mp[i][j] == 1) {mp[i][j] = 0;bfs(mp, i, j);res++;}}}cout << res << endl;
}
int main() {solve();return 0;
}

100.  岛屿的最大面积

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

代码随想录

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct node {int x, y;node(int x, int y) :x(x), y(y) {};
};
int res = 0;
queue<node>que;
void bfs(vector<vector<int>>&mp, int x, int y) {int total = 1;que.push(node(x, y));int dx[] = { 0,0,1,-1 };int dy[] = { -1,1,0,0 };while (!que.empty()) {node cur = que.front();que.pop();for (int i = 0; i < 4; i++) {int xx = cur.x + dx[i];int yy = cur.y + dy[i];if (xx < 0 || xx >= mp.size() || yy < 0 || yy >= mp[0].size() || mp[xx][yy] == 0)continue;mp[xx][yy] = 0;total++;que.push(node(xx, yy));}}res = max(res, total);
}
void solve() {int n, m;cin >> n >> m;vector<vector<int>>mp(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> mp[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (mp[i][j] == 1) {mp[i][j] = 0;bfs(mp, i, j);}}}cout << res << endl;
}
int main() {solve();return 0;
}