6 solutions
-
4
#include<bits/stdc++.h> using namespace std; const int N=1010; char g[N][N]; int dx[]={-1,-1,-1,0,0,1,1,1}; int dy[]={-1,0,1,-1,1,-1,0,1}; bool st[N][N]; int n,m; struct Node{ int x,y; }; void bfs(int x,int y) { queue<Node> q; q.push({x,y}); st[x][y]=1; while(q.size()) { Node t=q.front(); q.pop(); int x=t.x,y=t.y; for(int i=0;i<8;i++) { int a=x+dx[i],b=y+dy[i]; if(a<0||a>=n||b<0||b>=m) { continue; } if(g[a][b]=='.') { continue; } if(st[a][b]) { continue; } st[a][b]=1; q.push({a,b}); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>g[i]; } int res=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]=='W'&&!st[i][j]) { bfs(i,j); res++; } } } cout<<res; return 0; } -
2
#include<bits/stdc++.h> using namespace std; const int N=120; int dx[]={-1,0,1,-1,1,-1,0,1}; int dy[]={-1,-1,-1,0,0,1,1,1}; char g[N][N]; int n,m; bool cnt[N][N]; struct node{int x,y;}; void bfs(int x,int y) { cnt[x][y]=1; queue<node>q; q.push({x,y}); while(q.size()) { node t=q.front(); q.pop(); for(int i=0;i<8;i++) { int a=t.x+dx[i],b=t.y+dy[i]; if(g[a][b]=='.') { continue; } if(a<1||a>n||b<1||b>m) { continue; } if(cnt[a][b]) { continue; } q.push({a,b}); cnt[a][b]=1; } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>g[i][j]; } } int res=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(g[i][j]=='W'&&!cnt[i][j]) { bfs(i,j); res++; } } } cout<<res; return 0; } -
2
#include<bits/stdc++.h> using namespace std; const int N=1010; char g[N][N]; int dx[]={-1,-1,-1,0,0,1,1,1}; int dy[]={-1,0,1,-1,1,-1,0,1}; bool st[N][N]; int n,m; struct Node { int x,y; }; void bfs(int x,int y) { queue<Node> q; q.push({x,y}); st[x][y]=1; while(q.size()) { Node t=q.front(); q.pop(); int x=t.x,y=t.y; for(int i=0;i<8;i++) { int a=x+dx[i],b=y+dy[i]; if(a<0 || a>=n || b<0 || b>=m) { continue; } if(g[a][b]=='.') { continue; } if(st[a][b]) { continue; } st[a][b]=1; q.push({a,b}); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) { cin>>g[i]; } int res=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(g[i][j]=='W' && !st[i][j]) { bfs(i,j); res++; } } } cout<<res; return 0; } -
1
#include<bits/stdc++.h> using namespace std; int dx[]={-1,-1,-1,0,0,1,1,1}; int dy[]={-1,0,1,-1,1,-1,0,1}; struct PII{ int x,y; }; const int N=150; char g[N][N]; bool st[N][N]; int n,m; void bfs(int x,int y) { queue<PII> q; q.push({x,y}); st[x][y]=1; while(q.size()) { PII t=q.front(); q.pop(); for(int i=0;i<8;i++) { int a=t.x+dx[i],b=t.y+dy[i]; if(a<1||a>n||b<1||b>m) continue; if(g[a][b]=='.') continue; if(st[a][b]) continue; q.push({a,b}); st[a][b]=1; } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>g[i][j]; } } int cnt=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(st[i][j]==0&&g[i][j]=='W') { cnt++; bfs(i,j); } } } cout<<cnt; return 0; } -
-4
#include<bits/stdc++.h> using namespace std; const int N=1010; char g[N][N]; vector<int> dx[N]={0,-1,1,0,1,0,-1,1}; vector<int> dy[N]={0,-1,1,-1,-1,0,0,1}; int n,m,st[N][N]; struct Node{ int x,y; }; bool bfs(int x,int y,int q[N]) { q.push({x,-1}); q.push({y,-1}); st[0][0]=0; while(--q.size()) { Node t=q.size(); int f=q.top(); int x=f.x,y=f.y; for(int i=1;i<=q.x;i++) { int a=x+q[i],b=y+q[i]; if(x<0||a>=n||b<0||b>=m) break; if(st[a][b]=='M') break; if(q[a][b]) break; q[0][1]=1; q.push({-1,x}); q.push({-1,y}); } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>g[i]; int res; for(int i=0;i<n>>1;i++) { for(int j=i;j<m/i;j++) { if(st[i][j]=='W'&&q[i][j]) { bfs(q,res); res--; } } res++; } cout<<res; return 0; }
鸟嘴医生
LV 7
@ 2024-7-8 16:24:35
- 1