\(\mathcal{Description}\)
??Link.（HDU 裂开了先放个私链 awa。）
??在一个 \(n\times n\) 的方格图中，格子 \((i,j)\) 有权值 \(w_{i,j}\)，现可将一些不相邻的格子染黑，并保证白格子在四联通意义下存在哈密顿回路，方案的价值为染色格子权值之和。求方案的最大价值。
??\(n\le10\)，数据组数 \(T\le30\)。
\(\mathcal{Solution}\)
??Emmm...插头 DP 写得太少了，这题还算比较常规，所以只算记录一个板子叭。
??令 \(f(i,j,S)\) 表示正要考虑 \((i,j)\) 时，轮廓线为 \(S\) 的最大价值。轮廓上的每条边有四种状态：无插头、左插头、右插头、黑格子，大力转移即可，注意用 hash 保存状态。
??复杂度上界是 \(\mathcal O(n^34^{n+1})\)，但显然跑不满√
\(\mathcal{Code}\)
/*~Rainybunny~*/
#include <cstdio>
#include <cassert>
#include <cstring>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline void chkmax( int& a, const int b ) { a < b && ( a = b ); }
const int MAXN = 10;
int n, w[MAXN + 5][MAXN + 5];
struct HashTable {
static const int M = 299987;
int node, head[M + 5], nxt[M + 5], key[M + 5], val[M + 5];
inline void clear() {
rep ( i, 1, node ) head[key[i] % M] = 0;
node = 0;
}
inline void operator () ( const int s, const int v ) {
int h = s % M, las = 0;
for ( int i = head[h]; i; i = nxt[las = i] ) {
if ( key[i] == s ) {
return chkmax( val[i], v );
}
}
if ( !las ) head[h] = ++node;
else nxt[las] = ++node;
key[node] = s, val[node] = v, nxt[node] = 0;
}
} S[2];
inline int match( const int s, const int k ) {
int v = s >> k >> k & 3;
if ( v != 1 && v != 2 ) return -1;
if ( v == 1 ) {
int cnt = 1;
rep ( i, k + 1, n ) {
if ( int t = s >> i >> i & 3; t == 1 ) ++cnt;
else if ( t == 2 && !--cnt ) return i;
}
} else {
int cnt = 1;
per ( i, k - 1, 0 ) {
if ( int t = s >> i >> i & 3; t == 2 ) ++cnt;
else if ( t == 1 && !--cnt ) return i;
}
}
return assert( false ), -1;
}
inline bool check( const int s ) {
rep ( i, 0, n ) {
if ( ( s >> i >> i & 3 ) && ( s >> i >> i & 3 ) != 3 ) {
return false;
}
}
return true;
}
inline int solve() {
S[0].clear(), S[0]( 0, 0 );
int ret = 0;
for ( int i = 1, sta = 0; i <= n; ++i ) {
rep ( j, 1, S[sta].node ) {
int d = S[sta].key[j] >> n >> n;
assert( !d || d == 3 );
( S[sta].key[j] ^= d << n << n ) <<= 2;
}
for ( int j = 1; j <= n; ++j, sta ^= 1 ) {
S[!sta].clear();
rep ( k, 1, S[sta].node ) {
int s = S[sta].key[k], v = S[sta].val[k];
int pl = s << 2 >> j >> j & 3, pu = s >> j >> j & 3;
int ql = match( s, j - 1 ), qu = match( s, j );
s ^= ( pl << j << j >> 2 ) ^ ( pu << j << j );
if ( !pl && !pu ) { // b
S[!sta]( s | 15 << j << j >> 2, v + w[i][j] );
if ( i == n && j == n ) chkmax( ret, v + w[i][j] );
}
if ( i < n && j < n
&& ( !pl || pl == 3 ) && ( !pu || pu == 3 ) ) { // rd
S[!sta]( s | 9 << j << j >> 2, v );
}
if ( pl == 1 && pu == 2 && check( s ) ) { // lu, upd
if ( i == n && j == n ) chkmax( ret, v );
else if ( i == n && j == n - 1 && !( s >> n >> n & 3 ) ) {
chkmax( ret, v + w[n][n] );
}
}
if ( i < n && ( !pl || pl == 3 )
&& ( pu == 1 || pu == 2 ) ) { // u-d
S[!sta]( s | pu << j << j >> 2, v );
}
if ( j < n && ( pl == 1 || pl == 2 )
&& ( !pu || pu == 3 ) ) { // l-r
S[!sta]( s | pl << j << j, v );
}
if ( j < n && ( !pl || pl == 3 )
&& ( pu == 1 || pu == 2 ) ) { // u-r
S[!sta]( s | pu << j << j, v );
}
if ( i < n && ( pl == 1 || pl == 2 )
&& ( !pu || pu == 3 ) ) { // l-d
S[!sta]( s | pl << j << j >> 2, v );
}
if ( ~ql && ql != j && ~qu && qu != j - 1 ) { // lu
if ( pl == pu && pl == 1 ) {
S[!sta]( s ^ 3 << qu << qu, v );
} else if ( pl == pu && pl == 2 ) {
S[!sta]( s ^ 3 << ql << ql, v );
} else {
S[!sta]( s, v );
}
}
}
}
}
return ret;
}
int main() {
int T;
for ( scanf( "%d", &T ); T--; ) {
scanf( "%d", &n );
rep ( i, 1, n ) rep ( j, 1, n ) scanf( "%d", &w[i][j] );
printf( "%d\n", solve() );
}
return 0;
}