2019年华南理工大学程序设计竞赛（春季赛） E-数独挑战

（简单dfs，标记一下行，列，以及小块中出现的数，然后填数即可，这个要回溯。）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#define ll long long
using namespace std;
int mp[15][15],r[15][15],c[15][15],flag,vis[15][15];
//找到在哪个小块 
int getpos(int x,int y)
{
	if(x>=1&&x<=3)
	{
		if(y>=1&&y<=3)
			return 1;
		else if(y<=6)
		    return 2;
		else 
		    return 3;		
	}
	else if(x<=6)
	{
		if(y>=1&&y<=3)
			return 4;
		else if(y<=6)
		    return 5;
		else 
		    return 6;				
	}
	else
	{
		if(y>=1&&y<=3)
			return 7;
		else if(y<=6)
		    return 8;
		else 
		    return 9;	
	}
	
}
void dfs(int x,int y)
{
	if(flag) return ;
	if(mp[x][y])
	{
		if(x==9&&y==9)
		{
			flag=1;
			return ;
		}
		if(y==9)
		{
			dfs(x+1,1);
		}
		else
		{
			dfs(x,y+1);
		}	
	}
	else
	{
		for(int i=1;i<=9;i++)
		{
			if(!r[x][i]&&!c[y][i]&&!vis[getpos(x,y)][i])
			{
				vis[getpos(x,y)][i]=1;
				r[x][i]=1;
				c[y][i]=1;
				mp[x][y]=i;
				if(x==9&&y==9)
				{
					flag=1;
					return ;
				}
				if(y==9)
					dfs(x+1,1);
				else
					dfs(x,y+1);
				if(flag) return ;
				//回溯 
				r[x][i]=0;
				c[y][i]=0;
				mp[x][y]=0;	
				vis[getpos(x,y)][i]=0;			
			}
		}
		return ;
	}		
}
int main(void)
{
	flag=0;
	int f=1,sx,sy;
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			scanf("%d",&mp[i][j]);
			if(mp[i][j])
			{
				//标记该行中已出现的数 
				r[i][mp[i][j]]=1;
				//标记该列中已出现的数 
				c[j][mp[i][j]]=1;
				//标记该小块中已出现的数 
				vis[getpos(i,j)][mp[i][j]]=1;
				
			}
			else if(f)
			{
				sx=i;
				sy=j;
				f=0;
			}
		}
	}
	dfs(sx,sy);
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
			printf("%d%c",mp[i][j],j==9?'\n':' ');
	}
	return 0;	
}