搜索题
28.5%算法：
n=3，只要按顺序枚举棋盘上每个数字是多少，枚举完了之后n^2判断一下是否可行。时间复杂度：3^9*9^2
57%算法：
在顺序枚举的基础上每行每列开一个哈希表，记录每行每列哪些数字已经出现过了，搜索时跳过即可。
满分算法：
在57%的基础上记录每个连通块当前填的数字之积，然后判断当前填的数字是否可行。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct pos{
int x,y;
};
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int id[10][10],n,size[100],mul[100],p[10][10],cnt,ans,num[10][10],out[10][10];
bool vis[10][10],l[10][10],r[10][10];
void bfs(pos tmp,int cmp)
{
queue<pos>q;
q.push(tmp);
vis[tmp.x][tmp.y]=1,id[tmp.x][tmp.y]=cnt;
size[cnt]++;
while(!q.empty())
{
pos u=q.front();
q.pop();
for(int i=0;i<4;i++)
{
tmp.x=u.x+dx[i];
tmp.y=u.y+dy[i];
if(!vis[tmp.x][tmp.y]&&p[tmp.x][tmp.y]==cmp)
{
vis[tmp.x][tmp.y]=1,id[tmp.x][tmp.y]=cnt;
size[cnt]++;
q.push(tmp);
}
}
}
}
void dfs(int x,int y)
{
if(y==n+1)
x++,y=1;
if(x==n+1)
{
if(++ans==1)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
out[i][j]=num[i][j];
return;
}
if(size[id[x][y]]==1)
{
if(mul[id[x][y]]>n||l[x][mul[id[x][y]]]||r[y][mul[id[x][y]]])
return;
else
{
num[x][y]=mul[id[x][y]];
l[x][num[x][y]]=1;
r[y][num[x][y]]=1;
dfs(x,y+1);
l[x][num[x][y]]=0;
r[y][num[x][y]]=0;
return;
}
}
for(int i=1;i<=n;i++)
if(!l[x][i]&&!r[y][i]&&mul[id[x][y]]%i==0)
{
num[x][y]=i;
l[x][i]=1,r[y][i]=1;
mul[id[x][y]]/=i,size[id[x][y]]--;
dfs(x,y+1);
mul[id[x][y]]*=i,size[id[x][y]]++;
l[x][i]=0,r[y][i]=0;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&p[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!id[i][j])
{
mul[++cnt]=p[i][j];
bfs((pos){i,j},p[i][j]);
}
dfs(1,1);
printf("%d
",ans);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%d ",out[i][j]);
printf("
");
}
return 0;
}