学步园

原题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1019

简单的搜索题就是要小心一些：

#include<stdio.h>

typedef struct step
{
	int x,y;
	char direction;
}step;

step steps[10000];
int maps[101][101];
int m,n,flag;
int work(int x,int y,int mark)
{
	int i,j,xn,yn;
	char p;

	if(x<1||x>m||y<1||y>n||maps[x][y])return 0;
	if( mark == flag) return 1;
	xn = x; yn = y;
	for(i=steps[mark].x;i<=steps[mark].y;i++)
	{

		p=steps[mark].direction;
		if(p=='U')
		{
			xn=x-i;
			if(xn<1)	return 0;
			for(j=xn;j<=x;j++)
				if(maps[j][y])
				return 0;
		}
		if(p=='D')
		{
			xn=x+i;
			if(xn>m) return 0;
			for(j=x;j<=xn;j++)
				if(maps[j][y])
				return 0;
		}
		if(p=='R')
		{
			yn=y+i;
			if(yn>n)return 0;
			for(j=y;j<=yn;j++)
				if(maps[x][j])
				return 0;
		}
		if(p=='L')
		{
			yn=y-i;
			if(yn<1)	return 0;
			for(j=yn;j<=y;j++)
				if(maps[x][j])
				return 0;
		}
		if(work(xn,yn,mark+1)==1)
		return 1;
	}
	return 0;
}
int main()
{
	int k,t;
	int i,j,tx,ty;
	int count=0;
	char ch;
	scanf("%d",&k);
	while(k--)
	{
		t=0;count=0;flag=0;
		scanf("%d%d",&m,&n);
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
			scanf("%d",&maps[i][j]);
		while(1)
		{
			scanf("%d%d",&tx,&ty);
			if(tx==0 || ty==0)break;
			steps[t].x = tx;
			steps[t].y = ty;
			scanf(" %c",&ch);
			steps[t].direction = ch;
			t++;
			flag++;
		}

		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
				count += work(i,j,0);

		printf("%d\n",count);
	}

	return 0;

}