D. X-Sum

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Timur’s grandfather gifted him a chessboard to practice his chess skills. This chessboard is a grid $$$a$$$ with $$$n$$$ rows and $$$m$$$ columns with each cell having a non-negative integer written on it.

Timur’s challenge is to place a bishop on the board such that the sum of all cells attacked by the bishop is maximal. The bishop attacks in all directions diagonally, and there is no limit to the distance which the bishop can attack. Note that the cell on which the bishop is placed is also considered attacked. Help him find the maximal sum he can get.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 200$$$, $$$1 \leq m \leq 200$$$).

The following $$$n$$$ lines contain $$$m$$$ integers each, the $$$j$$$-th element of the $$$i$$$-th line $$$a_{ij}$$$ is the number written in the $$$j$$$-th cell of the $$$i$$$-th row $$$(0\leq a_{ij} \leq 10^6)$$$

It is guaranteed that the sum of $$$n\cdot m$$$ over all test cases does not exceed $$$4\cdot10^4$$$.

Output

For each test case output a single integer, the maximum sum over all possible placements of the bishop.

Example

input

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

output

Copy

1
2
3
4
20
1
5
3

Note

For the first test case here the best sum is achieved by the bishop being in this position:

img

笔者解析

译文大意：本题皇后可以吃他自己两斜边的值，包括自己本身，要找到皇后在哪一个位置时，能够吃到总和最大的数值

笔者思路： 皇后所在的点一定和两斜边有着某种关系，由题观察可知皇后的横行和竖行的变化确实存在某种关系。可发现皇后在竖列上的移动距离和皇后在横行上移动的距离时相等的，而且在横行还可以根据竖列移动的位置向两边移动，只要不超出数组范围就是可达的

笔者代码

java版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static int n,m;
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in) );
		int t = Integer.parseInt(reader.readLine());
		while(t-->0){
			String[] string = reader.readLine().split(" ");
			 n = Integer.parseInt(string[0]);
			 m = Integer.parseInt(string[1]);
			
			int[][] arr = new int[n][m];
			String[] strings =  new String [m];
			for(int i = 0;i<n;i++){
				strings = reader.readLine().split(" ");
				for(int j = 0;j < m;j++){
					arr[i][j] = Integer.parseInt(strings[j]);
				}
			}
			int ans = 0;
			
			for(int i = 0;i<n;i++){
				for(int j =0;j<m;j++){
					int now = -arr[i][j];//减去重复加的自身
					for(int k = 0;k<n;k++){
						int d = Math.abs(i-k);//此时遍历的行与原来实际行的距离差
						if(j-d>=0){
							now+=arr[k][j-d];//此时的左边列在距离差范围内
						}
						if(j+d<m){
							now+=arr[k][j+d];//此时右边列在距离范围内
						}
					}
					ans = Math.max(ans , now);
				}
			}
			System.out.println(ans);
		}
	}
	
}

c++版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
typedef long long LL;
int w[N][N];
int T,n,m;
 
LL get(int x,int y)
{
     int res=w[x][y];
     for(int i=1;i<=200;i++)
     {
         if(x-i>=1&&y-i>=1) res+=w[x-i][y-i];
         if(x+i<=n&&y+i<=m) res+=w[x+i][y+i];
         if(x+i<=n&&y-i>=1) res+=w[x+i][y-i];
         if(x-i>=1&&y+i<=m) res+=w[x-i][y+i];
     }
     return res;
}
 
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
          {
              scanf("%d", &w[i][j]);
          }
        LL res=0;  
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
          {
              res=max(res,get(i,j));
          }
          
        printf("%lld\n",res);
    }
    return 0;
}