爆搜AWA
#include<bits/stdc++.h>
using namespace std;
struct node{
int hang,_0;
};
node r[10];
int a[10][10],ans[10][10],vis[3][10][10],b[82],maxn,ok;//vis 0 1 2 宫行列
int cmp(node a,node b)
{
return a._0<b._0;
}
int gong(int x,int y)
{
if(x>=1&&x<=3){
if(y>=1&&y<=3) return 1;
else if(y>=4&&y<=6) return 2;
else return 3;
}
if(x>=4&&x<=6){
if(y>=1&&y<=3) return 4;
else if(y>=4&&y<=6) return 5;
else return 6;
}
if(x>=7&&x<=9){
if(y>=1&&y<=3) return 7;
else if(y>=4&&y<=6) return 8;
else return 9;
}
}
int score(int x,int y)
{
if(x==1||y==1||x==9||y==9) return 6;
else if(x==2||y==2||x==8||y==8) return 7;
else if(x==3||y==3||x==7||y==7) return 8;
else if(x==4||y==4||x==6||y==6) return 9;
else return 10;
}
int fen()
{
int cur=0;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cur+=ans[i][j]*score(i,j);
}
}
return cur;
}
void dfs(int s)
{
if(s==82){
ok=1;
maxn=max(maxn,fen());
return;
}
int x=b[s]/9+1;
int y=b[s]%9;
if(y==0)
x=b[s]/9,y=9;
if(!a[x][y]){
for(int i=1;i<=9;i++){
int k=gong(x,y);
if(!vis[0][k][i]&&!vis[1][x][i]&&!vis[2][y][i]){
ans[x][y]=i;
vis[0][k][i]=1,vis[1][x][i]=1,vis[2][y][i]=1;
dfs(s+1);
vis[0][k][i]=0,vis[1][x][i]=0,vis[2][y][i]=0;
}
}
}
else
dfs(s+1);
}
void inin(){
for(int i=1;i<=9;i++){
int cur=0;
for(int j=1;j<=9;j++){
cin>>a[i][j];
if(!a[i][j])
cur++;
else{
int v=a[i][j];
ans[i][j]=v;
int k=gong(i,j);
vis[0][k][v]=1,vis[1][i][v]=1,vis[2][j][v]=1;
}
}
r[i].hang=i,r[i]._0=cur;
}
sort(r+1,r+1+9,cmp);
int u=0;
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
int x=r[i].hang,y=j;
u++;
b[u]=(x-1)*9+y;
}
}
}
int main()
{
inin();
dfs(1);
if(ok)
cout<<maxn<<endl;
else
cout<<"-1"<<endl;
return 0;
}
舞蹈连板子
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=10000;
int r[N],l[N],u[N],d[N],row[N],col[N];
int h[N],s[N];
int ans,anss[N],cnt,n,m;
void inin(int _n,int _m){
n=_n;m=_m;
for(int i=0;i<=m;i++){
r[i]=i+1;
l[i]=i-1;
u[i]=d[i]=i;
}
r[m]=0;
l[0]=m;
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
cnt=m+1;
}
void cha(int R,int C){
s[C]++;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt;
row[cnt]=R;
col[cnt]=C;
if(h[R]<0){
h[R]=l[cnt]=r[cnt]=cnt;
}
else{
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
cnt++;
}
void remove(int c){
l[r[c]]=l[c];
r[l[c]]=r[c];
for(int i=d[c];i!=c;i=d[i]){
for(int j=r[i];j!=i;j=r[j]){
u[d[j]]=u[j];
d[u[j]]=d[j];
s[col[j]]--;
}
}
}
void resume(int c){
for(int i=u[c];i!=c;i=u[i]){
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
s[col[j]]++;
}
}
l[r[c]]=c;
r[l[c]]=c;
}
bool dance(int deep){
if(r[0]==0){
ans=deep;
return 1;
}
int c=r[0];
for(int i=r[0];i!=0;i=r[i]){
if(s[i]<s[c])c=i;
}
remove(c);
for(int i=d[c];i!=c;i=d[i]){
anss[deep]=row[i];
for(int j=r[i];j!=i;j=r[j])remove(col[j]);
if(dance(deep+1)==1)return 1;
for(int j=l[i];j!=i;j=l[j])resume(col[j]);
}
resume(c);
return 0;
}
int main(){
int x,y;
cin>>x>>y;
inin(x,y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>x;
if(x==1)cha(i,j);
}
}
if(dance(0)==0)cout<<"No Solution!"<<endl;
else{
for(int i=0;i<ans;i++){
cout<<anss[i]<<" ";
}
}
return 0;
}
舞蹈连解法
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=9*9*9+10;
const int M=9*9*4+100;
int pa[10][10];
struct node{
int r,c,v;
}nds[N*M];
int cnt,o,n,m,tot=1;
int l[N*M],r[N*M],u[N*M],d[N*M],row[N*M],col[N*M];
int h[N*M],s[N*M];
long long ans,anss[N*M],sum;
int volue[9][9]={
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};
void inin(int _n,int _m){
n=_n;m=_m;
for(int i=0;i<=m;i++){
r[i]=i+1;
l[i]=i-1;
u[i]=d[i]=i;
}
r[m]=0;
l[0]=m;
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
cnt=m+1;
}
void cha(int R,int C){
s[C]++;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt;
row[cnt]=R;
col[cnt]=C;
if(h[R]<0){
h[R]=l[cnt]=r[cnt]=cnt;
}
else{
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
cnt++;
}
void remove(int c){
l[r[c]]=l[c];
r[l[c]]=r[c];
for(int i=d[c];i!=c;i=d[i]){
for(int j=r[i];j!=i;j=r[j]){
u[d[j]]=u[j];
d[u[j]]=d[j];
s[col[j]]--;
}
}
}
void resume(int c){
for(int i=u[c];i!=c;i=u[i]){
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
s[col[j]]++;
}
}
l[r[c]]=c;
r[l[c]]=c;
}
void dance(int deep){
if(r[0]==0){
ans=deep;
long long ss=0;
int x,y,v;
for(int i=0;i<ans;i++){
x=nds[anss[i]].r;
y=nds[anss[i]].c;
v=nds[anss[i]].v;
ss+=(volue[x-1][y-1]*v);
}
sum=max(sum,ss);
return ;
}
int c=r[0];
for(int i=r[0];i!=0;i=r[i]){
if(s[i]<s[c])c=i;
}
remove(c);
for(int i=d[c];i!=c;i=d[i]){
anss[deep]=row[i];
for(int j=r[i];j!=i;j=r[j])remove(col[j]);
dance(deep+1);
for(int j=l[i];j!=i;j=l[j])resume(col[j]);
}
resume(c);
}
void addlink(int r,int c,int v){
cha(tot,(r-1)*9+c);
cha(tot,(9*9)+(r-1)*9+v);
cha(tot,(9*9*2)+(c-1)*9+v);
cha(tot,(9*9*3)+(((r-1)/3)*3+(c-1)/3)*9+v);
nds[tot].r=r,nds[tot].c=c,nds[tot].v=v;
tot++;
}
int main(){
inin(9*9*9,9*9*4);
for(int i=1;i<=9;i++){
for(int j=1;j<=9;j++){
cin>>o;
if(o==0){
for(int k=1;k<=9;k++){
addlink(i,j,k);
}
}
else{
addlink(i,j,o);
}
}
}
dance(0);
// for (int i = 0; i < ans; i++){
// int posr = anss[i];
// pa[nds[posr].r][nds[posr].c]= nds[posr].v;
// }
// for (int i = 1; i <= 9; i++){
// for (int j = 1; j <= 9; j++) printf("%d", pa[i][j]);
// printf("\n");
// }
// printf("\n");
if(sum)cout<<sum<<endl;
else cout<<-1;
return 0;
}