思路是这样的,读入数据,用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;
}

0 条评论

目前还没有评论...

信息

ID
1051
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
6196
已通过
2431
通过率
39%
被复制
13
上传者