#CF4034. 象的摆放
象的摆放
题目描述
光头强的祖父送给他一个棋盘来练习他的棋艺。这个棋盘是一个有 行和 列的网格 ,每个单元格上都有一个非负整数。
光头强的挑战是在棋盘上放置一个象,使象能攻击的所有网格的分值和达到最大。象向四个对角攻击,且可以攻击的距离没有限制。注意,象所在的网格也被认为受到了攻击。帮助光头强找到他能得到的最大总分。
输入格式
输入的第一行包含单个整数 表示测试用例的数量。测试用例描述如下。
每个测试用例的第一行包含整数 。
以下 行各包含 个整数,第 行的第 个元素 是写入第 行第 个单元格中的数字 。
保证所有测试用例的 总和不超过 。
输出格式
对于每个测试用例,输出一个整数,表示象能够攻击到的网格的分值和的最大值。
测试样例
4
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0
20
1
5
3
样例说明
对于这里的第一个测试用例,象处于这个位置时,可以获得最大和: