字节跳动笔试题（四）——连连看

矫情吗；* 2021-12-05 15:02 442阅读 0赞

### 连连看 ###

“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。  
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。

**输入：**  
输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。  
注意：询问之间无先后关系，都是针对当前状态的！

**输出：**  
每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。

### 题目思路 ###

对于这道题，是对连连看的一个模拟问题。其中又不是标准的连连看问题：这道题中不能从矩阵外部连线，同时连线的转弯数目不能超过两个。

这就是一个带有一定限制的dfs问题，直接引用网上更好的一个解法：

#include<stdio.h>
    #include<iostream>
    
    using namespace std;
    。 
    const int maxv=1010;
    const int inf=0xfffff;
    int n,m;
    int sx,sy,ex,ey;
    int g[maxv][maxv];
    int vis[maxv][maxv];
    bool flag;
    int fang[4][2]={
        {
        0,1},{
        0,-1},{
        1,0},{
        -1,0}};
    void dfs(int x,int y,int ans,int f)
    {
        
    	if(x==ex&&y==ey)
    	{
        
    		flag=1;
    	    return;
    	}
    	for(int i=0;i<4&&flag==0;i++)
    	{
        
    		int xx=x+fang[i][0],yy=y+fang[i][1];
    		if(xx>=1&&xx<=n&&yy<=m&&yy>=1&&(g[xx][yy]==0||(xx==ex&&yy==ey)))
    		{
        
    			if(i==f||f==-1)
    			{
        
    				vis[xx][yy]=ans;
    				dfs(xx,yy,ans,i);
    				if(flag==1)
    				return ;
    			}
    			else
    			if(ans<2&&vis[xx][yy]>vis[x][y])
    			{
        
    				vis[xx][yy]=ans+1;
    				dfs(xx,yy,ans+1,i);
    				if(flag)return;
    			}
    		}
    		
    	}
    }
    int main()
    {
        
         while(scanf("%d%d",&n,&m)!=EOF)
         {
        
         	if(n==0&&m==0)
         	break;
         	for(int i=1;i<=n;i++)
         	{
        
         		for(int j=1;j<=m;j++)
         		scanf("%d",&g[i][j]);
    		 }
    		 int p;
    		 scanf("%d",&p);
    		 while(p--)
    		 {
        flag=0;
    		 	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
    		 	if(g[sx][sy]!=g[ex][ey])
    		 	printf("NO\n");
    		 	else
    		 	if(g[sx][sy]==0)
    		 	printf("NO\n");
    		 	else
    		 	{
        
    		 	    fill(&vis[0][0],&vis[maxv][0],inf);
    		 	     vis[sx][sy]=0;
    		 	     dfs(sx,sy,0,-1);
    		 	     if(flag)
    		 	     printf("YES\n");
    		 	     else
    		 	     printf("NO\n");
    			 }
    		 }
    	 }
    }