1382.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"

char map[101][1001];
char key[101][101];
int r,c,n,m;
bool sign[2][1010],*sign1=sign[0],*sign2=sign[1];

void init() 
{
	int i;
	scanf("%d %d",&r,&c);
	for(i=0;i<r;i++)
		scanf("%s",key[i]);
	
	scanf("%d %d",&n,&m);
	
	for(i=0;i<=m-c;i++)
		sign1[i]=1;
	
}


int doit()
{
	int i,j,k,l,s;
	bool flag;
	
	for(i=0;i<=n+r;i++)
	{
		if(i<n)
			scanf("%s",map[i%r]);
		else for(j=0;j<m;j++)map[i%r][j]='.';
		
		
		for(j=0;j<=m-c;j++)
		if(sign1[j])
		{
			flag=1;
			for(k=0;k<r&&flag;k++)
			for(l=0;l<c;l++)
				if(i-r+1+k>=0&&map[(i-r+1+k)%r][j+l]=='#'&&key[k][l]=='#')
				{
					flag=0;
					break;
				}
			if(flag)sign2[j]=1;
			else sign2[j]=0;
		}

		for(j=0;j<m-c;j++)
		if(sign2[j]&&!sign2[j+1])
		{
			flag=1;
			for(k=0;k<r&&flag;k++)
			for(l=0;l<c;l++)
				if(i-r+1+k>=0&&map[(i-r+1+k)%r][j+l+1]=='#'&&key[k][l]=='#')
				{
					flag=0;
					break;
				}
			if(flag)sign2[j+1]=1;
		}
		
		for(j=m-c;j>0;j--)
		if(sign2[j]&&!sign2[j-1])
		{
			flag=1;
			for(k=0;k<r&&flag;k++)
			for(l=0;l<c;l++)
				if(i-r+1+k>=0&&map[(i-r+1+k)%r][j+l-1]=='#'&&key[k][l]=='#')
				{
					flag=0;
					break;
				}
			if(flag)sign2[j-1]=1;
		}
		
		for(j=0,s=0;j<=m-c;j++)
		{
			sign1[j]=sign2[j];
			s+=sign1[j];
		}
		if(s==0)break;
	}
	for(j=i+1;j<n;j++)
		scanf("%s",map[0]);
	return i;
}

int main()
{
	int t,ans;

	scanf("%d",&t);
	while(t--)
	{
		init();
		ans=doit();
		if(ans>=n+r)
			printf("The key can fall through.\n");
		else printf("The key falls to depth %d.\n",ans);
	}
	return 0;
}