WA on #4,9,10,13,15,17,18,20

似乎都是答案过小

code:

#include<bits/stdc++.h>
using namespace std;

const int PTS[15][15]={{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}};
struct node{
	int s,h;
}zr[15];
int a[15][15],ans=-1;
bool h[15][15],l[15][15],g[15][15];

bool cmp(node x,node y)
{
	return x.s<y.s;
}

void dfs(int now,int x,int y,int s)
{
    if(a[x][y])
    {
        if(now==9&&y==9)
        {
        	//for(int i=1;i<=9;i++){for(int j=1;j<=9;j++)cerr<<a[i][j]<<' ';cerr<<endl;}cerr<<endl;
        	ans=max(ans,s+a[x][y]*PTS[x-1][y-1]);
    		return;
		}
        if(y==9) dfs(now+1,zr[now+1].h,1,s+a[x][y]*PTS[x-1][y-1]);
        else dfs(now,x,y+1,s+a[x][y]*PTS[x-1][y-1]);
    }
    else
    {
        for(int i=1;i<=9;i++)
        {
            if(!h[x][i]&&!l[y][i]&&!g[(x-1)/3*3+(y-1)/3+1][i])
            {
                a[x][y]=i;
                h[x][i]=l[y][i]=g[(x-1)/3*3+(y-1)/3+1][i]=1;
                if(now==9&&y==9)
                {
                	//for(int i=1;i<=9;i++){for(int j=1;j<=9;j++)cerr<<a[i][j]<<' ';cerr<<endl;}cerr<<endl;
                	ans=max(ans,s+a[x][y]*PTS[x-1][y-1]);
    				return;
				}
                if(y==9) dfs(now+1,zr[now+1].h,1,s+a[x][y]*PTS[x-1][y-1]);
				else dfs(now,x,y+1,s+a[x][y]*PTS[x-1][y-1]);
                a[x][y]=h[x][i]=l[y][i]=g[(x-1)/3*3+(y-1)/3+1][i]=0;
            }
        }
    }
}

int main()
{
    for(int i=1;i<=9;i++)
    {
    	int s=0;
        for(int j=1;j<=9;j++)
        {
            cin>>a[i][j];
            s+=!a[i][j];
            if(a[i][j]) h[i][a[i][j]]=l[j][a[i][j]]=g[(i-1)/3*3+(j-1)/3+1][a[i][j]]=1;
        }
        zr[i].h=i;
        zr[i].s=s;
    }
    sort(zr+1,zr+10,cmp);
    //for(int i=1;i<=9;i++) cerr<<zr[i].h<<' '<<zr[i].s<<endl;cerr<<endl;
    dfs(1,zr[1].h,1,0);
    cout<<ans;
    return 0;
}