HDU 1175 连连看(dfs，bfs)

阳光穿透心脏的1/2处 2022-07-15 10:29 196阅读 0赞

题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=1175

dfs

一个重要的剪枝：当拐弯数为等于2时，判断目标点是否在那一列（行）的有效的范围内。

方向标记分别为0,1,2,3，在起始位置就开始做每个方向的标记。

code：

#include<stdio.h>
    #include<string.h>
    #include<iostream>
    using namespace std;
    int map[1001][1001];
    bool vis[1001][1001];
    int dx[]={-1,1,0,0};  
    int dy[]={0,0,-1,1}; 
    int n,m,k,x1,y1,x2,y2,flag;
    void dfs(int x,int y,int cnt,int dir)
    {
    	if(flag)
    		return ;
    	if(cnt>2)
    		return ;
    	if(x==x2&&y==y2)
    	{
    		flag=1;
    		return ;
    	}
    	if(vis[x][y]||x<0||x>=n||y<0||y>=m||map[x][y]!=0)
    		return ;
    	if(cnt==2)
    		if(!(dir==0&&y2==y&&x2<x||dir==1&&y2==y&&x2>x||dir==2&&x2==x&&y2<y||dir==3&&x2==x&&y2>y))
    			return ;
    	vis[x][y]=1;
    	for(int i=0;i<4;i++)
    	{
    		if(dir==i)
    			dfs(x+dx[i],y+dy[i],cnt,dir);
    		else
    			dfs(x+dx[i],y+dy[i],cnt+1,i);
    	}
    	vis[x][y]=0;
    }
    int main()
    {
    	while(cin>>n>>m,n,m)
    	{
    		for(int i=0;i<n;i++)
    			for(int j=0;j<m;j++)
    				cin>>map[i][j];
    		cin>>k;
    		while(k--)
    		{
    			cin>>x1>>y1>>x2>>y2;
    			x1-=1,y1-=1,x2-=1,y2-=1;
    			flag=0;
    			if((x1!=x2||y1!=y2)&&map[x1][y1]==map[x2][y2]&&map[x1][y1]!=0)
    			{
    				memset(vis,0,sizeof(vis));
    				vis[x1][y1]=1;
    				for(int i=0;i<4;i++)
    					dfs(x1+dx[i],y1+dy[i],0,i);	
    			}
    			if(flag)
    				cout<<"YES"<<endl;
    			else
    				cout<<"NO"<<endl;
    		}
    	}
    	return 0;
    }

bfs

code：

#include<iostream>
    #include<stdio.h>
    #include<queue>
    #include<limits.h>
    using namespace std;
    int direc[4][2] = {
       {0,1},{0,-1},{1,0},{-1,0}};//方向依次为右、左、下、上
    int a[1005][1005],visited[1005][1005],m,n;//a为输入的2维向量,visited记录该点是否被访问过了，同时记录有转折次数，如果
    //新的转折次数小于以前访问时的转折次数那么更新，否则就不更新。
    typedef struct
    {    
        int x,y,dir,corner;//x,y,为行数列数，dir为方向，corner为转角次数。
    }node;
    node start,end;//记录开始和结束
    void bfs()//宽度搜索
    {    
    	queue<node> q;
     	node cur,pre;   //用来记录当前的节点和前一个进行比较    
      	start.dir = -1;//开始时无方向
    	start.corner = 0;//开始时转角次数为0    
    	q.push(start);    
     	while(!q.empty())    
      	{        
       		pre = q.front();      
       		q.pop();        
       		if(pre.x == end.x && pre.y == end.y)        
         		{cout<<"YES"<<endl;return;}        
           	for(int i = 0; i < 4; i++)//对节点的四个方向分别进行判断        
            {            
                   cur.x = pre.x + direc[i][0];            
                   cur.y = pre.y + direc[i][1];            
                   cur.corner = pre.corner;      //令当前转角次数和前一个相同            
                   cur.dir = i;                  //当前方向            
                   //前一个不能使开始出，且当前方向和前一个方向不一致是转折次数自增1            
                   if(pre.dir != cur.dir&&pre.dir != -1) cur.corner++;            
                   //判断是否出界，转角次数是否超过限制            
                   if(cur.x<1||cur.y<1||cur.x>n||cur.y>m||cur.corner>2)continue;            
                   //如果当前位置有数字存在，且当前位置不是终结位置，违反规则            
                   if(a[cur.x][cur.y]&&!(cur.x==end.x&&cur.y==end.y))continue;            
                   if(cur.corner<visited[cur.x][cur.y])            
                   {                
                       visited[cur.x][cur.y] = cur.corner;                
                       q.push(cur);            
                   }        
     		}    
    	}    
     	cout<<"NO"<<endl;
    }  
    int main()
    {    
        int q;    
        while(scanf("%d%d",&n,&m),n,m)    
        {        
            for(int i = 1; i <= n; i++)        
            for(int j = 1; j <= m; j++)        
            scanf("%d",&a[i][j]);        
            scanf("%d",&q);        
            while(q--)        
            {            
                scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);            
                if(start.x==end.x&&start.y==end.y)//开始和结束在同一个位置            
                {cout<<"NO"<<endl;continue;}            
                //开始和结束位置没有数字或者开始和结束位置的数字不等。            
                if(!a[start.x][start.y]||!a[end.x][end.y]||(a[start.x][start.y]!=a[end.x][end.y]))            
                {cout<<"NO"<<endl;continue;}            
                for(int i = 1; i <= n; i++)            
                for(int j = 1; j <= m; j++)            
                visited[i][j] = INT_MAX;            
                bfs();        
            }    
        }    
        return 0;
    }