水题一道....要细心!!!

/*
 * tyvj-p1030 乳草的入侵
 * mike-w
 * 2011-10-26
 * ---------------------
 * simple flood fill
 * 注意左下角是(1,1)
 * url: http://tyvj.cpwz.cn/Problem_Show.asp?id=1030
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 110
#define QSIZE (SIZE*SIZE)

typedef struct _pos
{
	int x,y;
}pos;

char f[SIZE][SIZE];
int g[SIZE][SIZE];
pos q[QSIZE];
int qtail,qhead,qlen;
int xx,yy,sx,sy;
int d[8][2]={
	{1,1},{1,0},{1,-1},
	{0,1},{0,-1},{-1,1},
	{-1,0},{-1,-1}
};

int push(int x,int y)
{
	q[qtail].x=x;
	q[qtail].y=y;
	if(++qtail==QSIZE)
		qtail=0;
	qlen++;
	return 0;
}

int pop(int *x,int *y)
{
	*x=q[qhead].x;
	*y=q[qhead].y;
	if(++qhead==QSIZE)
		qhead=0;
	qlen--;
	return 0;
}

int flood_fill(void)
{
	int x,y,tx,ty,i;
	push(sx,sy);
	g[sx][sy]=0; /* 原来第一天不算... */
	while(qlen>0)
	{
		pop(&x,&y);
		for(i=0;i<8;i++)
		{
			tx=x+d[i][0];
			ty=y+d[i][1];
			if(tx>=0 && tx<xx && ty>=0 && ty<yy 
					&& f[tx][ty]=='.' && !g[tx][ty])
			{
				push(tx,ty);
				g[tx][ty]=g[x][y]+1;
			}
		}
	}
	return 0;
}

int main(void)
{
	int i,j,ans;
	freopen("in","r",stdin);	
	scanf("%d%d%d%d",&yy,&xx,&sy,&sx);
	sx=xx-sx;
	sy--;
	for(i=0;i<xx;i++)
		scanf("%s",f[i]);
	flood_fill();
	for(i=0,ans=0;i<xx;i++)
		for(j=0;j<yy;j++)
			if(ans<g[i][j])
				ans=g[i][j];
	printf("%d\n",ans);
	return 0;
}


 

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐