2434429_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int n, m, ans;
char map[201][201];
int mark[201][201];
int head[3][3], h;

int valid(int a,int b)
{
	if(a<0||b<0||a>=n||b>=m)
		return 0;
	return 1;
}

void flood_fill(int r,int c)
{
	mark[r][c] = -1;
	if(valid(r-1,c)&&mark[r-1][c]!=-1)
		flood_fill(r-1,c);
	if(valid(r+1,c)&&mark[r+1][c]!=-1)
		flood_fill(r+1,c);
	if(valid(r,c-1)&&mark[r][c-1]!=-1)
		flood_fill(r,c-1);
	if(valid(r,c+1)&&mark[r][c+1]!=-1)
		flood_fill(r,c+1);
}

int bfs(int r,int c)
{
	int num;
	int queue[40001][2];
	int f, p, tr, tc;

	mark[r][c] = 1;
	f = p = -1;
	queue[++f][0] = r,queue[f][1] = c;
	while(f!=p)
	{
		++p;num = 0;
		tr = queue[p][0],tc = queue[p][1];
		if(valid(tr-1,tc)&&map[tr-1][tc]=='1')
		{
			num++;
			if(mark[tr-1][tc]==0)
			{
				mark[tr-1][tc] = 1;
				queue[++f][0] = tr-1;
				queue[f][1] = tc;
			}
		}
		if(valid(tr,tc-1)&&map[tr][tc-1]=='1')
		{
			num++;
			if(mark[tr][tc-1]==0)
			{
				mark[tr][tc-1] = 1;
				queue[++f][0] = tr;
				queue[f][1] = tc-1;
			}
		}
		if(valid(tr+1,tc)&&map[tr+1][tc]=='1')
		{
			num++;
			if(mark[tr+1][tc]==0)
			{
				mark[tr+1][tc] = 1;
				queue[++f][0] = tr+1;
				queue[f][1] = tc;
			}
		}
		if(valid(tr,tc+1)&&map[tr][tc+1]=='1')
		{
			num++;
			if(mark[tr][tc+1]==0)
			{
				mark[tr][tc+1] = 1;
				queue[++f][0] = tr;
				queue[f][1] = tc+1;
			}
		}
		if(num>2)
		{
			flood_fill(tr,tc);
			return 0;
		}
		else
			if(num==1)
			{
				head[h][0] = tr;
				head[h][1] = tc;
				h++;
			}
	}
	return 1;
}

int check(int H)
{
	int r, c;
	int v1, v2, v3, v4, v5, v6, v7, v8;

	r = head[H][0];c = head[H][1];
	v1 = (!valid(r-1,c-1))||(map[r-1][c-1]=='0');
	v2 = (!valid(r-1,c+1))||(map[r-1][c+1]=='0');
	v3 = (!valid(r-2,c))||(map[r-2][c]=='0');
	v4 = (!valid(r,c-2))||(map[r][c-2]=='0');
	v5 = (!valid(r+1,c-1))||(map[r+1][c-1]=='0');
	v6 = (!valid(r+2,c))||(map[r+2][c]=='0');
	v7 = (!valid(r+1,c+1))||(map[r+1][c+1]=='0');
	v8 = (!valid(r,c+2))||(map[r][c+2]=='0');
	if(valid(r-1,c)&&map[r-1][c]!='1'&&v1&&v2&&v3)
		return 1;
	if(valid(r+1,c)&&map[r+1][c]!='1'&&v5&&v6&&v7)
		return 1;
	if(valid(r,c-1)&&map[r][c-1]!='1'&&v5&&v1&&v4)
		return 1;
	if(valid(r,c+1)&&map[r][c+1]!='1'&&v7&&v2&&v8)
		return 1;
	return 0;
}

void solve()
{
	int i, j;

	for(i = 0; i < n; i++)
		for(j = 0; j < m; j++)
			if(map[i][j]=='1'&&mark[i][j]==0)
			{
				h = 0;
				if(bfs(i,j)&&!check(0)&&!check(1))
					ans++;
			}
}

int main()
{
	int i;

	while(scanf("%d%d",&n,&m)==2)
	{
		if(n==m&&n==0)
			break;
		for(i = 0; i < n; i++)
			scanf("%s",map[i]);
		memset(mark,0,sizeof(mark));
		ans = 0;
		solve();
		printf("%d\n",ans);
	}
	return 1;
}