| 比赛 | 暑假培训B班二测 | 评测结果 | AAAAAAAA | 
    | 题目名称 | 劣质的草 | 最终得分 | 100 | 
    | 用户昵称 | Citron酱 | 运行时间 | 0.097 s | 
    | 代码语言 | C++ | 内存使用 | 15.61 MiB | 
    | 提交时间 | 2012-07-22 09:58:16 | 
显示代码纯文本
#include <cstdio>
#define I_F "badgras.in"
#define O_F "badgras.out"
const int MAXn=1000+2;
const short R[8][2]={{ 1,-1},{ 1, 0},{ 1, 1},
					 { 0,-1},		 { 0, 1},
					 {-1,-1},{-1, 0},{-1, 1}};
struct stack
{
	int x,y;
	short r;
};
int n,m;
long map[MAXn][MAXn]={{0}};
long ans=0;
stack s[MAXn*MAXn];
void Input();
void Dfs(const int&, const int&);
void Search();
void Output();
int main()
{
	Input();
	Search();
	Output();
	return 0;
}
void Input()
{
	freopen(I_F,"r",stdin);
	scanf("%d%d",&n,&m);
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j)
			scanf("%ld",&map[i][j]);
}
void Dfs(const int &x, const int &y)
{
//	map[x][y]=0;
//	for (short i=0; i<8; ++i)
//		if (map[x+R[i][0]][y+R[i][1]]>0)
//			Dfs(x+R[i][0], y+R[i][1]);
	long top=1;
	map[x][y]=0;
	s[0].x=x;
	s[0].y=y;
	s[0].r=0;
	bool flag;
	while (top>0)
	{
		flag=true;
		for (short i=s[top-1].r; i<8; ++i)
			if (map[s[top-1].x+R[i][0]][s[top-1].y+R[i][1]]>0)
			{
				map[s[top-1].x+R[i][0]][s[top-1].y+R[i][1]]=0;
				s[top-1].r=i+1;
				s[top].x=s[top-1].x+R[i][0];
				s[top].y=s[top-1].y+R[i][1];
				s[top].r=0;
				++top;
				flag=false;
				break;
			}
		if (flag)
			--top;
	}
}
void Search()
{
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j)
			if (map[i][j]>0)
				++ans,
				Dfs(i,j);
}
void Output()
{
	freopen(O_F,"w",stdout);
	printf("%ld\n",ans);
}