Yajilin
TimeLimit:5000MS MemoryLimit:262144KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
You are given a $n\times n$ rectangular grid of squares. You want to color some cells to black, such that
- Black cells do not touch each other orthogonally(they do not share a side).
- We can draw a single continuous non-intersecting loop that passes through each cell that is not black. The loop must "enter" each cell from the centre of one of its four sides and "exit" from a different side; all turns are 90 degrees.
The following is an example.
In this problem, the weight of cells $(i,j) (1\leq i,j \leq n)$ is $w_{i,j}$. You want to color some cells black, and maximize the sum of weights of these cells.
- Black cells do not touch each other orthogonally(they do not share a side).
- We can draw a single continuous non-intersecting loop that passes through each cell that is not black. The loop must "enter" each cell from the centre of one of its four sides and "exit" from a different side; all turns are 90 degrees.
The following is an example.
In this problem, the weight of cells $(i,j) (1\leq i,j \leq n)$ is $w_{i,j}$. You want to color some cells black, and maximize the sum of weights of these cells.
Input
The first line contains an integer $T(1\leq T\leq 30)$- the number of test cases.
For each test case, the first line contains an integer $n(2\leq n\leq 10)$ , each of the following $n$ lines contains $n$ integers $w_{i,j} (0\leq w_{i,j}\leq 10^6)$. The $j$-th number in the $i$-th line indicates the weight of cells in the $i$-th row and the $j$-th column.
For each test case, the first line contains an integer $n(2\leq n\leq 10)$ , each of the following $n$ lines contains $n$ integers $w_{i,j} (0\leq w_{i,j}\leq 10^6)$. The $j$-th number in the $i$-th line indicates the weight of cells in the $i$-th row and the $j$-th column.
Output
For each test case, output a number - the answer.
SampleInput
2 3 9 8 7 8 8 2 10 4 7 4 7 5 2 4 3 3 5 4 2 2 7 1 8 9 6 8
SampleOutput
10 28