解题思路
FloodFill
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
const int N=310;
typedef pair<int,int> PII;
char g[N][N];
int st[N][N];
int a[N][N];
int T,n;
int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
void get_num()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(g[i][j]=='*')
{
st[i][j]=true;
a[i][j]=1;
continue;
}
int cnt=0;
for(int k=0;k<8;k++)
{
int xx=i+dx[k],yy=j+dy[k];
if(xx<0||xx>=n||yy<0||yy>=n)
continue;
if(g[xx][yy]=='*')
cnt++;
}
a[i][j]=cnt;
}
}
void bfs(int x,int y)
{
queue<PII> q;
q.push({x,y});
st[x][y]=true;
while(q.size())
{
auto t=q.front();
q.pop();
int xx=t.x,yy=t.y;
// cout<<xx<<"-"<<yy<<endl;
for(int i=0;i<8;i++)
{
int aa=xx+dx[i],bb=yy+dy[i];
if(aa<0||aa>=n||bb<0||bb>=n)
continue;
if(!st[aa][bb])
{
st[aa][bb]=true;
if(!a[aa][bb])
{
q.push({aa,bb});
}
}
}
}
}
int main()
{
cin>>T;
for(int t=1;t<=T;t++)
{
cin>>n;
memset(g,0,sizeof g);
memset(st,0,sizeof st);
memset(a,0,sizeof a);
for(int i=0;i<n;i++)
cin>>g[i];
get_num();
int cnt=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(!st[i][j]&&!a[i][j])
{
bfs(i,j);
cnt++;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(!st[i][j])
{
st[i][j]=true;
cnt++;
}
printf("Case #%d: %d\n",t,cnt);
}
return 0;
}