HDU 1175 连连看 (DFS)

雨点打透心脏的1/2处 2022-06-08 09:50 304阅读 0赞

//题意自己看，不懂度娘
    #include <stdio.h>
    #include <string.h>
    int map[1010][1010];//数组范围要注意，有个很蠢的人就错在这(不是我)
    int visit[1010][1010];
    int x,y,sx,sy,ex,ey;
    int dicx[]={1,-1,0,0};
    int dicy[]={0,0,1,-1};
    bool flag;
    int n,m,k;
    void DFS(int x,int y,int dic,int turns)
    {
    	if(turns>2||flag)//转弯次数大于2或者已走 
    		return ;
    	if(turns==2&&((x-ex)!=0&&(y-ey)!=0))//剪枝，判断两次转向后两个对应点是否在同一直线上 
    		return ;	
    	if(x==ex&&y==ey&&turns<=2)//位置符合且转弯小于2 
    	{
    		flag=1;
    		return ;
    	}
    	for(int i=0;i<4;++i)//四方向循环 
    	{
    		int xx=x+dicx[i];
    		int yy=y+dicy[i];//移动后新的坐标 
    		if(xx<1||yy<1||xx>n||yy>m||visit[xx][yy])//是否越界，剪枝 
    		continue;
    		if(map[xx][yy]==0||(xx==ex&&yy==ey))//新坐标未走过或者新坐标为对应点坐标 
    		{
    			visit[xx][yy]=1;//标为1表示走过 
    			if(dic==-1||dic==i)//dic表示方向，用来表示两个对应点是否在同一个直线上。dic的变化与turns有关。 
    			DFS(xx,yy,i,turns);两个坐标在同一直线上，往下走时转弯次数不需要加一
    			else
    			DFS(xx,yy,i,turns+1);//dic不为-1或者i说明两点不在同一直线，往下走时转弯次数需要加一 
    			visit[xx][yy]=0;//没有找到，撤回 
    		}
    	}
    	return ;
    } 
    int main(int argc, char *argv[])
    {
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		if(n==0&&m==0)
    		break;
    		memset(map,0,sizeof(map));
    		for(int i=1;i<=n;++i)
    			for(int j=1;j<=m;++j)
    				scanf("%d",&map[i][j]);
    		scanf("%d",&k);
    		for(int i=0;i<k;++i)
    		{
    			scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    			memset(visit,0,sizeof(visit));
    			flag=0;
    			if(map[sx][sy]==map[ex][ey]&&map[sx][sy])//查看两个坐标点是否相同 
    			DFS(sx,sy,-1,0);//将初始方向设为-1后开始DFS 
    			if(flag)
    			printf("YES\n");
    			else
    			printf("NO\n");
    		}
    	}
    	return 0;
    }
    //修订注释版1.0
    //Start-ZJ
    //2017/9/21/ 18:20