蒟蒻只希望懂得,为啥开O2会 WA ?
#include <iostream>
#include <algorithm>
using namespace std;
int yx[10],ixy,a[10][10];
bool h[10][10],l[10][10],g[10][10],flag;
struct node{
int cnt,id;
}c[10];
bool cnt(node a,node b){
return a.cnt<b.cnt;
}
struct m{
int x,y;
}w[10];
bool cnt2(m a,m b){
if(a.x!=b.x) return yx[a.x]<yx[b.x];
else return a.y<b.y;
}
void dfs(int id){
if(flag){
return ;
}
if(id==ixy+1){
for(int i = 1;i <= 9;i++){
for(int j = 1;j <= 9;j++){
cout << a[i][j] << " ";
}
cout << endl;
}
flag=1;
return ;
}
for(int i = 1;i <= 9;i++){
if(!h[w[id].x][i] && !l[w[id].y][i] && !g[(w[id].x-1)/3*3+(w[id].y-1)/3+1][i]){
h[w[id].x][i]=1;
l[w[id].y][i]=1;
g[(w[id].x-1)/3*3+(w[id].y-1)/3+1][i]=1;
a[w[id].x][w[id].y]=i;
dfs(id+1);
h[w[id].x][i]=0;
l[w[id].y][i]=0;
g[(w[id].x-1)/3*3+(w[id].y-1)/3+1][i]=0;
}
}
}
int main(){
for(int i = 1;i <= 9;i++){
c[i].id=i;
for(int j = 1;j <= 9;j++){
cin >> a[i][j];
if(!a[i][j]){
c[i].cnt++;
w[++ixy].x=i;
w[ixy].y=j;
}
else{
h[i][a[i][j]]=1;
l[j][a[i][j]]=1;
g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
}
}
}
sort(c+1,c+10,cnt);
for(int i = 1;i <= 9;i++){
yx[c[i].id]=i;
}
sort(w+1,w+10,cnt2);
dfs(1);
return 0;
}