5 条题解
-
6
BFS
连通块的最好的解决方法就是BFS，对于每一个1我们都进行一次BFS，把连通的1变成0，答案就是BFS后的1的个数
- 问题①：坐标如何存储？我们可以用pair或者结构体
- 问题②：BFS如何实现？我们把每个为1的点放到队列中，尝试前后左右走，假如走到1就将其放到队列中。注意vis的标记
#include <bits/stdc++.h> using namespace std; const int N = 105; typedef pair<int,int> PII; int g[N][N]; bool vis[N][N]; int n,m,cnt; //方向数组 int tx[] = {0,0,1,-1},ty[] = {1,-1,0,0}; //BFS过程 void bfs(int a,int b) { queue<PII> q; q.push({a,b}); while(!q.empty()) { auto t = q.front(); q.pop(); int x = t.first,y = t.second; //尝试扩展 for(int i=0;i<4;i++) { int rx = x+tx[i],ry = y+ty[i]; vis[x][y] = false; //判断是否越界以及是否为1 if(g[rx][ry] == 1 && vis[rx][ry] && rx>=1 && rx<=n && ry>=1 && ry<=m) { g[rx][ry] = 0; q.push({rx,ry}); } } } } int main() { memset(vis,true,sizeof(vis)); cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> g[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) //对于每一个1都进行一次BFS if(g[i][j] == 1) { bfs(i,j); cnt++; } cout << cnt; return 0; }DFS
对于选考班我觉得还是DFS最能想出来，我们还是对于每个1进行扩展，但是我们不用队列，而是直接递归到下一个点，同时打上标记
#include <bits/stdc++.h> using namespace std; const int N = 105; typedef pair<int,int> PII; int g[N][N]; bool vis[N][N]; int n,m,cnt; //方向数组 int tx[] = {0,0,1,-1},ty[] = {1,-1,0,0}; //DFS void dfs(int a,int b) { //打标记 vis[a][b] = false; for(int i=0;i<4;i++) { int rx = a+tx[i],ry = b+ty[i]; //扩展并且判断 if(rx>=1 && rx<=n && ry>=1 && ry<=m && g[rx][ry] == 1 && vis[rx][ry]) { g[rx][ry] = 0; //递归 dfs(rx,ry); } } } int main() { memset(vis,true,sizeof(vis)); cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> g[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(g[i][j] == 1) { //对于每一个1都进行一次DFS dfs(i,j); cnt++; } cout << cnt; return 0; }-
qianmo @ 2023-3-16 14:03:43
别问我为什么不发Python的
-
Florance
@ 2023-3-16 18:48:49
-
-
Python
# DFS N = 105 vis = [[True for i in range(N)] for i in range(N)] n,m = 0,0 cnt = 0 g = [] tx = [0,0,1,-1];ty = [1,-1,0,0] def dfs(a,b): vis[a][b] = False for i in range(4): rx = a+tx[i];ry = b+ty[i] if 0<=rx<n and 0<=ry<m: if g[rx][ry] == 1 and vis[rx][ry]: g[rx][ry] = 0 dfs(rx,ry) n,m = map(int,input().split()) for i in range(n): g.append(list(map(int,input().split()))) for i in range(n): for j in range(m): if g[i][j] == 1: dfs(i,j) cnt+=1 print(cnt)# BFS from queue import Queue N = 105 vis = [[True for i in range(N)] for i in range(N)] n,m = 0,0 cnt = 0 g = [] tx = [0,0,1,-1];ty = [1,-1,0,0] def bfs(a,b): q = Queue() q.put([a,b]) while not q.empty(): t = q.get() x = t[0];y = t[1] for i in range(4): rx = x+tx[i];ry = y+ty[i] vis[x][y] = False if 0<=rx<n and 0<=ry<m: if g[rx][ry] == 1 and vis[rx][ry]: g[rx][ry] = 0 q.put([rx,ry]) n,m = map(int,input().split()) for i in range(n): g.append(list(map(int,input().split()))) for i in range(n): for j in range(m): if g[i][j] == 1: bfs(i,j) cnt+=1 print(cnt)
-
2
这么多大佬发了题解，本蒟蒻也来发一下
- 核心思想是采用递归的方式进行DFS
- 标记已访问节点的方式是将g数组中对应位置的值改为0
- 时间复杂度为
O(nm) -
- 和上面qianmo大佬比起来虽然时间复杂度都是
O(nm)，但不必要调用vis
- 和上面qianmo大佬比起来虽然时间复杂度都是
C++
#include <bits/stdc++.h> using namespace std; const int N = 105; int g[N][N]; int n, m, cnt; void dfs(int x, int y){ if (g[x][y] == 0) return;// 已经访问过的点直接返回 g[x][y] = 0; // 标记为已访问 if (x > 1) dfs(x-1, y); if (x < n) dfs(x+1, y); if (y > 1) dfs(x, y-1); if (y < m) dfs(x, y+1); } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> g[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (g[i][j] == 1){ dfs(i, j); cnt++; } cout << cnt << endl; return 0; }Python
①
n, m = map(int, input().split()) g = [[0]*(m+1) for i in range(n+1)] cnt = 0 def dfs(x, y): if g[x][y] == 0: return g[x][y] = 0 if x > 1: dfs(x-1, y) if x < n: dfs(x+1, y) if y > 1: dfs(x, y-1) if y < m: dfs(x, y+1) for i in range(1, n+1): line = input().split() for j in range(1, m+1): g[i][j] = int(line[j-1]) for i in range(1, n+1): for j in range(1, m+1): if g[i][j] == 1: dfs(i, j) cnt += 1 print(cnt)②
Pycharm逼的码风，
同样的代码，只是想告诉你我恨Pycharmn, m = map(int, input().split()) g = [[0]*(m+1) for i in range(n+1)] cnt = 0 def dfs(x, y): if g[x][y] == 0: return g[x][y] = 0 if x > 1: dfs(x-1, y) if x < n: dfs(x+1, y) if y > 1: dfs(x, y-1) if y < m: dfs(x, y+1) for i in range(1, n+1): line = input().split() for j in range(1, m+1): g[i][j] = int(line[j-1]) for i in range(1, n+1): for j in range(1, m+1): if g[i][j] == 1: dfs(i, j) cnt += 1 print(cnt)都看到这了还不点个赞🙃
-
2
C++
不要脸地发个蓝翔优化题解#include <bits/stdc++.h> using namespace std; typedef pair <int, int> PII; const int N = 105; int g[N][N]; int n ,m, cnt = 0; int tx[4] = {1, -1, 0, 0}; int ty[4] = {0, 0, 1, -1} void BFS(int x, int y){ queue <PII> q; q.push({x, y}); while(!q.empty()) { PII t = q.front(); q.pop(); int a = t.first; int b = t.second; for(int i = 0; i < 4; i++) { int rx = a + tx[i]; int ry = b + ty[i]; if(rx >= 1 && ry >= 1 && g[rx][ry] == 1) { g[rx][ry] = 0; q.push({rx, ry}); } } } } int main(){ cin >> n >> m; for(int i = 1; i <= m; i++) { for(int j = 1; j <= m; j++) { cin >> g[i][j]; } } for(int i = 1; i <= m; i++) { for(int j = 1; j <= m; j++) { if(g[i][j] == 1) { BFS(i ,j); cnt += 1; } } } cout << cnt; return 0; }-
哈哈上课写的AC刚好下课，现在看来写了很多不必要的东西
-
-
1
《关于题目数据太水以至于递归能过这件事》
#include <bits/stdc++.h> using namespace std; int sq[1000][1000]; int dir[5][2] = {{}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int cnt = 2; int l, w; void b(int x, int y) { for (int i = 1; i <= 4; i++) { int x1 = x + dir[i][1]; int y1 = y + dir[i][0]; if (1 <= x1 <= l and 1 <= y1 <= w and sq[x1][y1] == 1) { sq[x1][y1] = cnt; b(x1, y1); } } } signed main() { ios::sync\_with\_stdio(0); cin.tie(0); cin >> l >> w; for (int i = 1; i <= l; i++) { for (int j = 1; j <= w; j++) { cin >> sq[i][j]; } } for (int i = 1; i <= l; i++) { for (int j = 1; j <= w; j++) { if (sq[i][j] == 1) { b(i, j); cnt++; } } } cout<<cnt-2; }-
这就是dfs的flood fill写法
-
-
0
def bfs(x,y): que=[[x,y]] step=[[1,0],[-1,0],[0,1],[0,-1]] while que!=[]: p=que.pop(0) a[p[0]][p[1]]=0 for i in step: nx=p[0]+i[0];ny=p[1]+i[1] if 0<=nx<n and 0<=ny<m and a[nx][ny]==1: que.append([nx,ny]) n,m=map(int,input().split()) a=[] for i in range(n): a.append(list(map(int,input().split()))) #print(a) ans=0 for i in range(n): for j in range(m): if a[i][j]==1: ans+=1 bfs(i,j) # print(ans,a) print(ans)
- 1