TOJ 4972: 数独 4*4 dfs

落日映苍穹つ 2022-04-13 07:27 198阅读 0赞

**描述**

预计的周末天气非常不错，小T和小伙伴在满足的吃完烧烤后，玩起了数独。所谓数独就是在N\*N的表格上填补数字，使得每行每列每块上都存在1~N这N个不同的数字。不过这是小T临时找的表格，所以只有4\*4的大小。

对于4\*4的表格，它的每行上都应该含有1~4四个数字，每列上也含有1~4四个数字。然后将其分为4份2\*2的小块，每个小块也含有1~4这4个数字。一个满足要求的数独表格如下所示：

1 2 **|** 4 3

3 4 **|** 2 1

一一一一

2 3 **|** 1 4

4 1 **|** 3 2

那么问题来了，给你一张没填完的4\*4表格，请问你能将它填完吗？

**输入**

输入第一行包含一个T，代表一共包含T组数据。

每组数据包含四行四列的表格，每个数字之间以空格隔开。其中Aij代表第i行第j列的数字，如果Aij=?则说明该处还没有填上数字。

每组数据之间含有一个空行。

保证Aij∈\{1,2,3,4,?\}。

**输出**

每组数据输出占一行。

如果表格可以被填满则输出Yes，否则输出No。

具体格式见样例。

**样例输入**

3  
1 ? ? 3  
? ? 2 1  
2 3 ? ?  
4 ? 3 2

1 ? ? 4  
? 1 ? ?  
2 ? ? ?  
? 4 ? ?

1 ? 4 3  
? 2 ? ?  
2 1 ? ?  
4 ? ? 2

**样例输出**

Case \#1: Yes  
Case \#2: No  
Case \#3: No

数独规则：横向，纵向，2\*2的小方格里，1-4各出现一次。（2\*(i/2)+j/2是计算在第几个小方格里）

题意：判断可否完成数独，dfs中如果可以走到最后（flag=1）说明可行。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int a[20][20],flag;
    int r[20][20],l[20][20],s[20][20];//r行 l列 s小方阵 
    void dfs(int i,int j)
    {
    	if(i==4&&j==0)
    	flag=1;	
    	else
    	{
    		if(a[i][j]!=0)
    		{
    			if(j<3)
    			dfs(i,j+1);
    			else
    			dfs(i+1,0);
    		}
    		else
    		{
    			for(int k=1;k<=4;k++)
    			{
    				if(!r[i][k]&&!l[j][k]&&!s[2*(i/2)+j/2][k])
    				{
    					a[i][j]=k;
    					r[i][k]=1;
    					l[j][k]=1;
    					s[2*(i/2)+j/2][k]=1;
    					if(j<3)
    					dfs(i,j+1);
    					else
    					dfs(i+1,0);
    					if(flag)return;
    					//回溯重置 
    					a[i][j]=0;
    					r[i][k]=0;
    					l[j][k]=0;
    					s[2*(i/2)+j/2][k]=0;
    				}
    			}
    		}
    	}
    }
    int main()
    {
    	int t,i,j,o=1;
    	char aa;
    	scanf("%d",&t);
    	while(t--)
    	{
    		memset(r,0,sizeof r);
    		memset(l,0,sizeof l);		
    		memset(s,0,sizeof s);
    		for(i=0;i<4;i++)
    		{
    			for(j=0;j<4;j++)
    			{
    				getchar();
    				scanf("%c",&aa);
    				if(aa=='?')
    				a[i][j]=0;
    				else
    				a[i][j]=aa-'0';								
    				if(a[i][j])
    				{
    					r[i][a[i][j]]=1;
    					l[j][a[i][j]]=1;
    					s[2*(i/2)+j/2][a[i][j]]=1;
    				}
    			}
    		}			
    		flag=0;
    		dfs(0,0);
    		if(flag)
    		printf("Case #%d: Yes\n",o++);
    		else
    		printf("Case #%d: No\n",o++);
    		getchar();
    	}
    }