poj-2676sudoku

逃离我推掉我的手 2022-06-09 04:09 140阅读 0赞

![Image 1][]

思路：深搜， 主要是判断是否在同一行，同一列，同一格。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10;
    const int INF=0x3f3f3f3f;
    int T, cnt;
    int mp[maxn][maxn], row[maxn][maxn], col[maxn][maxn], grid[maxn][maxn];
    int zero[maxn*maxn][2];
    
    int location(int i, int j)
    {
    	return ((i-1)/3)*3+(j-1)/3+1;
    }
    
    int dfs(int step)
    {
    	if(step==cnt+1)
    	return 1;
    	for(int i=1; i<=9; i++)
    	{
    		if(!row[zero[step][0]][i] && !col[zero[step][1]][i] && !grid[location(zero[step][0], zero[step][1])][i])
    		{
    			row[zero[step][0]][i]=1;
    			col[zero[step][1]][i]=1;
    			grid[location(zero[step][0], zero[step][1])][i]=1;
    			mp[zero[step][0]][zero[step][1]]=i;
    			if(dfs(step+1))
    			return 1;
    			row[zero[step][0]][i]=0;
    			col[zero[step][1]][i]=0;
    			grid[location(zero[step][0], zero[step][1])][i]=0;
    		}
    	}
    	return 0;
    		
    }
    
    int main(){
    	cin>>T;
    	while(T--)
    	{
    		cnt=0;
    		memset(col, 0, sizeof(col));
    		memset(row, 0, sizeof(row));
    		memset(grid, 0, sizeof(grid));
    		for(int i=1; i<=9; i++)
    		{
    			for(int j=1; j<=9; j++)
    			{
    				scanf("%1d", &mp[i][j]);
    				if(mp[i][j])
    				{
    					row[i][mp[i][j]]=1;
    					col[j][mp[i][j]]=1;
    					grid[location(i, j)][mp[i][j]]=1;
    				}
    				else
    				{
    					zero[++cnt][0]=i;
    					zero[cnt][1]=j;			
    				}	
    			}
    		}
    		dfs(1);
    		for(int i=1; i<=9; i++)
    		{
    			for(int j=1; j<=9; j++)
    			cout<<mp[i][j];
    			cout<<endl;
    		}
    	}
    	return 0;
    }

[Image 1]: