代码随想录第五十七天

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; }