1164.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 90 行

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000

#if debug
    #define NMAX 10
#else
    #define NMAX 53
#endif
int m,n;
char a[NMAX][NMAX];
char b[NMAX][NMAX]={0};
char d[4]={1,2,4,8};
int xp[4]={-1,0,1,0};
int yp[4]={0,-1,0,1};
int tr(int x,int y)
{
	int num=0;
	if(b[y][x]==1)
		return 0;
	b[y][x]=1;
	for(int i=0;i<4;i++)
	{
		if((a[y][x]&d[i])==0)
		{
			num+=tr(x+xp[i],y+yp[i]);
		}
	}
	return num+1;
}
int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d%d",&m,&n);
	int i,j;
	int no=0,max=0;
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	for(i=0;i<=m+1;i++)
	{
		b[i][0]=1;
		b[i][n+1]=1;
	}
	for(i=0;i<=n+1;i++)
	{
		b[0][i]=1;
		b[m+1][i]=1;
	}

	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(!b[i][j])
			{
				no++;
				int tmp=tr(j,i);
				if(max<tmp)
					max=tmp;
			}
		}
	}
	printf("%d\n",no);
	printf("%d",max);
	
#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}