靶形数独

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#define N 10
using namespace std;
int a[N][N],tot,ans,res,nxt;
int zer[N];
struct ptn
{
int x,y;
}b[N * N];
int v[N][N] = {
{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 bel[N][N] = {
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
};
int cnt1[N][N];
int cnt2[N][N];
int cnt3[N][N];
inline bool cmp(ptn a,ptn b)
{
return zer[a.x] < zer[b.x];
}
inline void dfs(int q)
{
if (q >= nxt)
{
ans = max(ans,res);
if ((double)clock() / CLOCKS_PER_SEC > 0.98)
{
printf("%d",ans);
exit(0);
}
return;
}
int xx = b[q + 1].x,yy = b[q + 1].y;
for(int j = 9;j >= 1;j--)
{
a[xx][yy] = j;
if (cnt1[xx][j] || cnt2[yy][j] || cnt3[bel[xx][yy]][j])
{
continue;
}
cnt1[xx][a[xx][yy]] = 1;
cnt2[yy][a[xx][yy]] = 1;
cnt3[bel[xx][yy]][a[xx][yy]] = 1;
tot++;
res += v[xx][yy] * j;
dfs(q + 1);
tot--;
res -= v[xx][yy] * j;
cnt1[xx][a[xx][yy]] = 0;
cnt2[yy][a[xx][yy]] = 0;
cnt3[bel[xx][yy]][a[xx][yy]] = 0;
a[xx][yy] = 0;
}
}
signed main()
{
for (int i = 1;i <= 9;i++)
{
for (int j = 1;j <= 9;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j])
{
tot++,res += v[i][j] * a[i][j];
int xx = i,yy = j;
cnt1[xx][a[xx][yy]] = 1;
cnt2[yy][a[xx][yy]] = 1;
cnt3[bel[xx][yy]][a[xx][yy]] = 1;
}
if(!a[i][j])b[nxt] = (ptn){i,j},zer[i];
}
}
sort(b + 1,b + nxt + 1,cmp);
dfs(0);
if (ans == 0)
{
puts("-1");
}
else
{
printf("%d",ans);
}
return 0;
}