题目描述
blablabla
样例
blablabla
include[HTML_REMOVED]
using namespace std;
int ans[5][5],a[5][5],vis[10];
pair[HTML_REMOVED]p[10];
int n=0,cnt=0;
bool check(){
int sum=a[1][1]+a[2][2]+a[3][3];
if(sum!=(a[1][3]+a[2][2]+a[3][1]))return false;
for(int i=1;i<=3;i){
int t1=0,t2=0;
for(int j=1;j<=3;j){
t1+=a[i][j],t2+=a[j][i];
}
if(t1!=sum||t2!=sum) return false;
}
return true;
}
void dfs(int u){
if(u>n){
if(check()){
cnt;
for(int i=1;i<=n;i){
for(int j=1;j<=3;j){
ans[i][j]=a[i][j];
}
}
}
return ;
}
int x=p[u].first,y=p[u].second;
for(int k=1;k<=9;k){
if(vis[k])continue;
vis[k]=1;
a[x][y]=k;
dfs(u+1);
vis[k]=0;
a[x][y]=0;
}
}
signed main(){
for(int i=1;i<=3;i){
for(int j=1;j<=3;j){
cin>>a[i][j];
if(!a[i][j]){
p[++n]=make_pair(i,j);}
else vis[a[i][j]]=1;
}}
dfs(1);
if(cnt ==1){
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
cout<<ans[i][j]<<" ";
if(j==3)puts("");
}
}
}
else cout<<"Too Many";
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla