比赛 暑假培训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);
}