HDU 1426 Sudoku Killer (DFS)

水深无声 2022-06-08 14:39 148阅读 0赞

//题意自己看，不会度娘

#include <stdio.h>
    struct mmp
    {
    	int x;
    	int y;
    }we[81];//结构体代表数独图里的坐标 
    int map[9][9],num,flag;
    
    int cheak(int k,int step)//k代表放入的数，检查在9*9和3*3的图中，行和列里是否有相同的数 
    {
    	int i,j;
    	for(i=0;i<9;i++)
    		if(map[we[step].x][i]==k||map[i][we[step].y]==k)//检查在9*9的图里是否有同行或者同列的数 
    			return 0;
    	int x=we[step].x/3*3;//很神奇的优化，计算属于哪个9宫格   检查在9宫格中是否数据冲突 
    	int y=we[step].y/3*3;//计算在9*9里的坐标放在3*3的坐标中是在哪 
    	for(i=0;i<3;i++)
    		for(j=0;j<3;j++)
    			if(map[x+i][y+j]==k)//检查是否在3*3的图里有同行或者同列 
    				return 0;
    				return 1;		
    } 
    
    void DFS(int step)
    {
    	int i,j;
    	if(step==num)//符合 
    		{
    			for(i=0;i<9;i++)
    				{
    					for(j=0;j<8;j++)
    						printf("%d ",map[i][j]);
    						printf("%d\n",map[i][8]);
    				}//输出结果 
    			flag=1;
    			return ;	
    		}
    	for(i=1;i<=9;i++)
    		{
    			if(cheak(i,step)&&!flag)//同行同列都没有相同的数且数没被用过 
    			{
    				map[we[step].x][we[step].y]=i;//标记 
    				DFS(step+1);
    				map[we[step].x][we[step].y]=0;
    			}	
    		}
    		return ; 
    }
    int main(int argc, char *argv[])
    {
    int i,j;
    int skt=0;
    char a[3];
    while(scanf("%s",a)!=EOF)//scanf自动忽略回车，所以不用处理数据之间的空行
    {
    	num=0;
    	if(a[0]=='?')//处理第一行第一位
    		{
    			we[num].x=0;
    			we[num].y=0;
    			num++;
    			map[0][0]=0;
    		}
    	else
    		map[0][0]=a[0]-'0';//转为数字 
    	for(i=0;i<9;i++)
    		{
    			for(j=0;j<9;j++)
    				{
    					if(i==0&&j==0)
    						continue;
    					scanf("%s",a);
    					if(a[0]=='?')//以？开始进行DFS 
    						{
    							map[i][j]=0;
    							we[num].x=i;
    							we[num].y=j;
    							num++;
    						}
    					else
    					map[i][j]=a[0]-'0';	
    				}
    		}
    	flag=0;
    	if(skt++)//两组之间输出空格 
    	printf("\n");
    	DFS(0);		
    }	
    	return 0;
    }

//Start-ZJ

//2017/9/28/14:08