代码1 模拟队列
typedef pair<int, int> PII; //定义坐标的数据结构
const int N=1010,M=N*N;
int n,m;
char g[N][N]; //记录地图信息
PII q[M]; //pair类为二元组,所以要开N*N
bool st[N][N]; //记录每个点的状态
void bfs(int sx, int sy)
{
int hh=0,tt=0;
q[0]={sx,sy}; //将第一个点入队
st[sx][sy]=true;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
while(hh<=tt)//当队列不空
{
auto t=q[hh++];//取出队头元素 然后将其出队
for(int i=0;i<8;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=0 && x<n && y>=0 && y<m && g[x][y] == 'W' && !st[x][y])
{
q[++tt]={x,y}; //新坐标(x,y)入队
st[x][y]=true;
}
}
}
}
//for循环也可以写成二重循环 循环内部代码不一样,但起相同效果
for(int i=t.first-1;i<=t.first+1;i++)
for(int j=t.second-1;j<=t.second+1;j++)
{
if(i == t.first && j==t.second) continue;
if(i<0 || i>=n || j<0 || j>=m) continue;
if(g[i][j]=='.' || st[i][j]) continue;
q[++tt]={i,j};
st[i][j]=true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",g[i]);
int cnt=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);
cnt++;
}
printf("%d",cnt);
return 0;
}
代码2 STL队列
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N=1010,M=N*N;
int n,m;
char g[N][N];
bool st[N][N];
queue<PII> q;
void bfs(int sx, int sy)
{
q.push({sx,sy});
st[sx][sy]=true;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<8;i++)
{
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=0 && x<n && y>=0 && y<m && g[x][y] == 'W' && !st[x][y])
{
q.push({x,y}); //新坐标(x,y)入队
st[x][y]=true;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",g[i]);
int cnt=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);
cnt++;
}
printf("%d",cnt);
return 0;
}