和之前做过的填数独的题目相似，要想DFS的去填写数独的话最关键之处就在于如何进行行与不行的判断。根据游戏规则如果一个数可填那么就需要横和竖以及所在的宫格里面没有相同的数。那么就得采用HASH散列的方式去记录下某一行，某一列以及某一个宫格里面有哪些数。在这里为了方便使用宫格与每一个之间的映射所以提前打表了一个gong_table的数组用于实现映射。
然后这道题复杂在需要求出数值最大的某一种填法，那么最暴力做法就是将所有的填法都搜索出来取最大的那个值。但毫无疑问会超时。
在DFS的搜索树里面越是开头节点少的数最后这棵树也就越小。所以在这里面根据能够填写的数的可能性，先从可能性少的来填起，会使搜索树变小。
通过这一点优化就过了。感觉优化的有点随便。。。。。可能是数据不够强的缘故，应该会有更好的解法。 
//如果能经过排序之后按照从中间向外走的顺序去填的话，那么遍历的时候从9到1进行遍历，得到的第一个结果应该就是正确的结果。
#include <bits/stdc++.h>

using namespace std;
struct Node {
    int x, y;
    int val;
}node[9*9];
const int maxn = 10;
int ans = -1;
int cnt = 0;
int a[maxn][maxn];
bool vertical[maxn][maxn];
int vertical_num[maxn];
bool across[maxn][maxn];
int across_num[maxn];
bool gong[maxn][maxn];
int gong_num[maxn];
int total;
int mp[maxn][maxn];
int gong_table[10][10] {
    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 sort_table[10][10]{
    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,
};

bool comp(Node n1, Node n2) {
//     return vertical_num[n1.y]+across_num[n1.x]>vertical_num[n2.y]+across_num[n2.x];
//     if (vertical_num[n1.y]==vertical_num[n2.y]) return across_num[n1.x]>across_num[n2.x];
//     return vertical_num[n1.y]>vertical_num[n2.y];
    if (across_num[n1.x]==across_num[n2.x]) return vertical_num[n1.y]>vertical_num[n2.y];
    return across_num[n1.x]>across_num[n2.x];
}

int calc() {
    int num = 0;
    for (int i=1;i<=9;i++) {
        for (int j=1;j<=9;j++) {
            num += mp[i][j]*sort_table[i][j];
        }
    }
    return num;
}

void DFS(int pos, int num) {
    if (pos==cnt) {
        ans = max(ans, num+total);
        return ;
    }
    for (int i=9;i>=1;i--) {
        int x = node[pos].x;int y = node[pos].y;
        if (!vertical[y][i]&&!across[x][i]&&!gong[gong_table[x][y]][i]) {
            vertical[y][i] = true;
            across[x][i] = true;
            gong[gong_table[x][y]][i] = true;
            DFS(pos+1, num+i*sort_table[x][y]);
            vertical[y][i] = false;
            across[x][i] = false;
            gong[gong_table[x][y]][i] = false;
        }
    }
}

int main() {
    int k;
    for (int i=1;i<=9;i++) {
        for (int j=1;j<=9;j++) {
            cin>>k;
            mp[i][j] = k;
            if (k) {
                vertical[j][k] = true;
                vertical_num[j]++;
                across[i][k] = true;
                across_num[i]++;
                gong[gong_table[i][j]][k] = true;
                gong_num[gong_table[i][j]]++;
            } else {
                node[cnt].x = i;
                node[cnt].y = j;
                node[cnt].val = k;
                cnt++;
            }
        }
    }
    sort(node, node+cnt, comp);
    total = calc();
    DFS(0, 0);
    cout<<ans;
    return 0;
}