在找深搜顺序的时候,vis1数组的值会改变/jk 求各位dalao看看orz
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=15;
int p[maxn][maxn]={
{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}
};
int a[maxn][maxn],tot;
struct node
{
int pos,num;
}c[maxn];
struct point{
int x,y;
}q[maxn];
bool cmp(node x,node y)
{
return x.num<y.num;
}
int vis1[maxn][maxn];
int vis2[maxn][maxn];
int vis3[maxn][maxn],ff=-1;
long long ans,res=-1;
void dfs(int step,long long sum)
{
ff=max(ff,step);
if(step==tot+1)
{
if(sum>res)
res=sum;
return;
}
for(int i=1;i<=9;i++)
{
int xx=q[step].x;
int yy=q[step].y;
int pos=(xx-1)/3*3+(yy-1)/3+1;
if(vis1[xx][i]||vis2[yy][i]||vis3[pos][i])
continue;
vis1[xx][i]=1;
vis2[yy][i]=1;
vis3[pos][i]=1;
dfs(step+1,sum+1ll*i*p[xx][yy]);
vis1[xx][i]=0;
vis2[yy][i]=0;
vis3[pos][i]=0;
}
}
int main(){
for(int i=1;i<=9;i++)
{
c[i].pos=i;
for(int j=1;j<=9;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]!=0)
{
ans+=1ll*a[i][j]*p[i][j];
vis1[i][a[i][j]]=1;
vis2[j][a[i][j]]=1;
vis3[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
}
else
{
c[i].num++;
}
}
}
sort(c+1,c+10,cmp);
//----------就是下面这个循环----
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
if(a[c[i].pos][j]==0)
{
++tot;
q[tot].x=c[i].pos;
q[tot].y=j;
}
}
}
//----------就是上面这个数组------
dfs(1,ans);
printf("%lld",res);
return 0;
}