hdoj1175——连连看

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1175
用dfs思路比较简单,我用了一个比较土的办法来判是否转弯,就是传入该点的前一点坐标和前前一点坐标,前前一点坐标和该点坐标x、y值分别不等,则说明转弯。
用了一个剪枝,当已经转了两次弯时,判断现在所在点的x、y坐标分别与目标点x、y坐标不等,则说明至少还得转一次才能到达目标点,舍去。
后来在网上看到此题还可以用bfs求解,每次把转这次弯可以到达的所有点入队。

#include<stdio.h>
#include<stdlib.h>
int map[1005][1005];
bool visit[1005][1005];
int a[5],b[5];
bool flag=false;
int xb,yb,xd,yd;
void dfs(int xs,int ys,int xpre,int ypre,int xprepre,int yprepre,int turn)
{
	int i,j;
	visit[xs][ys]=true;
	if(xs!=xprepre && ys!=yprepre)
		turn++;
	if(turn>2)
		return;
	if(turn==2)
	{
		if(xs!=xd && ys!=yd)
			return;
	}
	if(xs==xd && ys==yd && turn<=2)
	{
		flag=true;
		return;
	}
	for(i=1;i<=4;i++)
	{
		if(!visit[xs+a[i]][ys+b[i]] &&(map[xs+a[i]][ys+b[i]]==0 || (map[xs+a[i]][ys+b[i]]==map[xb][yb] && xs+a[i]==xd && ys+b[i]==yd))&& !flag)//开始没写&& xs+a[i]==xd && ys+b[i]==yd,导致起始点与目标点以及其间的数全相同时会产生错误
		{
			
				dfs(xs+a[i],ys+b[i],xs,ys,xpre,ypre,turn);
				visit[xs+a[i]][ys+b[i]]=false;
		
		}
	}
return;
}

int main()
{
	int n,m,q;
	a[1]=-1,b[1]=0;
	a[2]=0,b[2]=-1;
	a[3]=1,b[3]=0;
	a[4]=0,b[4]=1;
	scanf("%d %d",&n,&m);
	while(n!=0 || m!=0)
	{
		int i,j,k;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&map[i][j]);

			}
		scanf("%d",&q);
		int x1,y1,x2,y2;
		for(int r=1;r<=q;r++)
		{
			flag=false;
			int turn=0;
			for(i=0;i<=n+1;i++)
				for(j=0;j<=m+1;j++)
					visit[i][j]=true;
			for(i=1;i<=n;i++)
				for(j=1;j<=m;j++)
					visit[i][j]=false;
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			xd=x2;
			yd=y2;
			xb=x1;
			yb=y1;
			if(map[xb][yb]==map[xd][yd] && map[xb][yb]!=0 && !(xb==xd && yb==yd))
				dfs(x1,y1,x1,y1,x1,y1,turn);
			if(flag)
				printf("YES\n");
			else
				printf("NO\n");
		
		}
		scanf("%d %d",&n,&m);
	}


//system("pause");
return 0;
}