比赛 20121016 评测结果 AWWWWWWWWW
题目名称 家族 最终得分 10
用户昵称 苏轼 运行时间 0.013 s
代码语言 C++ 内存使用 2.98 MiB
提交时间 2012-10-16 21:43:27
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n=0,w[105][205]={0},m,answer=0,used[105][205]={0};
int f[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
void bfs(int x,int y);
int main()
{
	freopen ("family.in","r",stdin);
	freopen ("family.out","w",stdout);
	string ss;
	getline(cin,ss);
	for (int i=0;i<ss.size();i++)
	{
		if (ss[i]>='0'&&ss[i]<='9')
		{
			n=n*10+(ss[i]-'0');
		}
	}
	for (int i=1;i<=n;i++)
	{
		string s;
		getline(cin,s);
		m=s.size();
		for (int j=0;j<m;j++)
		{
			if (s[j]>='a'&&s[j]<='z')
			{
				w[i][j+1]=1;
			}
			else
			{
				w[i][j+1]=0;
				used[i][j+1]=1;
			}
		}
	}
	/*for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (w[i][j])
				cout<<1;
			else
				cout<<0;
		}
		cout<<endl;
	}
	*/
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (!used[i][j])
			{
				used[i][j]=1;
				bfs(i,j);
				answer++;
			}
		}
	}
	cout<<answer;
	return 0;
}
/*
void dfs(int x,int y)
{
	for (int i=0;i<4;i++)
	{
		int xx,yy;
		xx=x+f[i][0];
		yy=y+f[i][1];
		if (xx<1||xx>n||yy<1||yy>m||used[xx][yy])
			continue;
		used[xx][yy]=1;
		dfs(xx,yy);
	}
}
*/

void bfs(int x,int y)
{
	int q[20005][2]={0};
	int tou,wei;
	tou=wei=0;
	q[tou][0]=x;
	q[tou][1]=y;
	while (tou<=wei)
	{
		for (int i=0;i<4;i++)
		{
			int xx,yy;
			xx=q[tou][0]+f[i][0];
			yy=q[tou][1]+f[i][1];
			if (xx<1||xx>n||yy<1||yy>m||used[xx][yy])
				continue;
			used[xx][yy]=1;
			wei++;
			q[wei][0]=xx;
			q[wei][1]=yy;
		}
		tou++;
	}
}