P1074 靶形数独

思路

类似数独的dfs回溯
如果0多的话，搜不过去
这里的优化很优秀，就是先搜0少的一行，在搜0多的一行
这样可以减少dfs的次数,跑的还挺快的
noip2018rp++

压行代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
int ans=-1,a[10][10],f[10][10],vis[10][10],h[10][10],l[10][10],zz[10];;
inline int get(int x,int y) {return (x-1)/3*3+(y-1)/3+1;}
void dfs(int id,int x,int y) {
    if(x==0) {
        int tmp=0;
        FOR(i,1,9) FOR(j,1,9) tmp+=f[i][j]*a[i][j];
        ans=max(ans,tmp);
        return;
    }
    if(a[x][y]) if(y==1) dfs(id-1,zz[id-1],9);else dfs(id,zz[id],y-1);
    else FOR(i,1,9) {
        if(vis[get(x,y)][i]||h[x][i]||l[y][i]) continue;
        vis[get(x,y)][i]=1;h[x][i]=1;l[y][i]=1;a[x][y]=i;
        if(y==1) dfs(id-1,zz[id-1],9);
        else dfs(id,zz[id],y-1);
        vis[get(x,y)][i]=0;h[x][i]=0;l[y][i]=0;a[x][y]=0;
    }
}
struct node {
    int id,gs;
    bool operator < (const node &b) const {return gs<b.gs;}
}hel[10];
int main() {
    FOR(i,1,9) FOR(j,1,9) f[i][j]=10-max(abs(i-5),abs(j-5));
    FOR(i,1,9) FOR(j,1,9) {
        cin>>a[i][j];
        hel[i].gs+=(bool)a[i][j],hel[i].id=i;
        if(a[i][j]) vis[get(i,j)][a[i][j]]=1;h[i][a[i][j]]=1;l[j][a[i][j]]=1;
    }
    sort(hel+1,hel+10);
    FOR(i,1,9) zz[i]=hel[i].id;
    dfs(9,zz[9],9);
    cout<<ans<<"\n";
    return 0;
}