题目:题意:有一块N×M的土地,雨后积起了水,有水标记为‘W’,干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼?
```#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[1001][1001];
int dx[8]={0,1,0,-1,-1,1,-1,1};
int dy[8]={1,0,-1,0,-1,-1,1,1};
int q[1000001][3];
int cnt;
void bfs(int x,int y)
{
int h,t;
h==t==1;
q[t][1]=x;
q[t][2]=y;
a[x][y]='.';
while(h<=t)
{
for(int i=0;i<8;i++)
{
int nx=q[h][1]+dx[i];
int ny=q[h][2]+dy[i];
if(a[nx][ny]=='W')
{
t++;
q[t][1]=nx;
q[t][2]=ny;
a[nx][ny]='.';
}
}
h++;
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='W')
{
cnt++;
bfs(i,j);
}
}
}
cout<<cnt<<endl;
return 0;
}
离谱,刚刚做完这道题,我把代码给你看吧,你自己看看看哪里错了
#include<bits/stdc++.h>
using namespace std;
int a[121][121];
bool vst[121][121];
int n, m;
struct node{int x; int y;};
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
void bfs(int x, int y) {
queue<node>q;
q.push({x, y});
vst[x][y] = true;
while (q.size()) {
node ft = q.front();
q.pop();
for (int i = 0; i < 8; ++i) {
int xx = ft.x + dx[i];
int yy = ft.y + dy[i];
if (a[xx][yy] == 0) continue;
if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
if (vst[xx][yy]) continue;
// cout << xx << " " << yy << endl;
vst[xx][yy] = true;
q.push({xx, yy});
}
}
}
int main(){
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
char c;
cin >> c;
if (c == 'W') a[i][j] = 1;
else a[i][j] = 0;
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!vst[i][j] && a[i][j] == 1) {
++cnt;
bfs(i, j);
}
}
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= m; ++j) {
// cout << vst[i][j];
// }
// cout << endl;
// }
cout << cnt << endl;
return 0;
}
#include<cstdio>
int n,m;
char a[120][120];
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,1},{1,1},{1,-1},{-1,-1}};
struct node
{
int x;
int y;
}q[100000];
void bfs(int x0,int y0)
{
int head=1,tail=1;
a[x0][y0]='.';
q[tail].x=x0;
q[tail].y=y0;
tail++;
while(head<tail)
{
int x=q[head].x;
int y=q[head].y;
for(int i=0;i<8;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]=='W')
{
a[nx][ny]='.';
q[tail].x=nx;
q[tail].y=ny;
tail++;
}
}
head++;
}
}
int main()
{
int sum=0;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",a[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]=='W')
{
sum++;
bfs(i,j);
}
printf("%d\n",sum);
return 0;
}