- 送给圣诞夜的极光
- 2015-02-03 23:17:04 @
思路是这样的,读入数据,用bool型数组存储,如果是#则b[i][j]为true,ans+1,然后宽搜,如果找到第一个点为true,则标记为false,然后12个方向拓展,每找到一个点加到队列,同时标记这个点为false,求为什么过不去啊.........
#include<iostream>
#include<string>
using namespace std;
struct p
{
int x,y;
};
p t[1000000];
bool b[101][101];
int n,m,ans;
string s;
void search(int xx,int yy)
{
int head,top,k,x,y;
head=1;top=0;
t[head].x=xx;
t[head].y=yy;
do
{
top++;
x=t[top].x;
y=t[top].y;
if (x-2>0) if (b[x-2][y])
{
head++;
b[x-2][y]=false;
t[head].x=x-2;
t[head].y=y;
};
if (x-1>0) if (b[x-1][y])
{
head++;
b[x-1][y]=false;
t[head].x=x-1;
t[head].y=y;
};
if ((x-1>0)&&(y-1>0)) if (b[x-1][y-1])
{
head++;
b[x-1][y-1]=false;
t[head].x=x-1;
t[head].y=y-1;
};
if (y-1>0) if (b[x][y-1])
{
head++;
b[x][y-1]=false;
t[head].x=x;
t[head].y=y-1;
};
if (y-2>0) if (b[x][y-2])
{
head++;
b[x][y-2]=false;
t[head].x=x;
t[head].y=y-2;
};
if ((x-1>0)&&(y+1<=m)) if (b[x-1][y+1])
{
head++;
b[x-1][y+1]=false;
t[head].x=x-1;
t[head].y=y+1;
};
if ((x+1<=n)) if (b[x+1][y])
{
head++;
b[x+1][y]=false;
t[head].x=x+1;
t[head].y=y;
};
if (x+2<=n) if (b[x+2][y])
{
head++;
b[x+2][y]=false;
t[head].x=x+2;
t[head].y=y;
};
if ((x+1<=n)&&(y+1<=m)) if (b[x+1][y+1])
{
head++;
b[x+1][y+1]=false;
t[head].x=x+1;
t[head].y=y+1;
};
if (y+1<=m) if (b[x][y+1])
{
head++;
b[x][y+1]=false;
t[head].x=x;
t[head].y=y+1;
};
if (y+2<=m) if (b[x][y+2])
{
head++;
b[x][y+2]=false;
t[head].x=x;
t[head].y=y+2;
};
if ((x+1<=n)&&(y-1>0)) if (b[x+1][y-1])
{
head++;
b[x+1][y-1]=false;
t[head].x=x+1;
t[head].y=y-1;
};
}while (top<head);
};
int main()
{
cin>>n>>m;
for (int i=0;i<=100;i++)
for (int j=0;j<=100;j++)
b[i][j]=false;
for (int i=1;i<=n;i++)
{
cin>>s;
for (int j=0;j<=m-1;j++)
if (s[j]=='#'){ b[i][j]=true; };
};
ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (b[i][j])
{
search(i,j);
ans++;
};
cout<<ans<<endl;
return 0;
}