题意：
给你一个n* n的矩阵，还有一个k，要你找一个起点坐标，然后上下左右四个方向走k步，然后计算他们的和，使得这个和最大化。
思路：
一开始写了一个bfs，O(n^4)超时，然后改了一下。然后观察了一下最后我们要求的和是一个菱形，如果这个菱形内的和可以O(1)计算这题O(n ^ 3)就过了，但是菱形的和不太好算，我们让坐标轴旋转45°，这样就变成这个矩形，然后前缀和就可以计算了。旋转45度怎么弄？(x,y) -> (x + y - 1, n - x + y)，这样就可以了，通俗的讲坐标轴旋转45度就是让矩阵中所有对角线旋转45度，矩阵中所有对角线元素满足x + y 相等，然后相加他们就在同一行了，列的话相减就行了，防止负数+n即可。然后再处理一下细节，这题就出来了。
代码:

#include<bits/stdc++.h>
using namespace std;

int s[500 * 2][500 * 2] = {0};
int a[500 * 2][500 * 2] = {0};
int getsum(int x1,int y1,int x2,int y2){
	return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
void sloved(){
	int n,k;cin>>n>>k;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin>>a[i][j];
			s[i + j - 1][n - i + j] = a[i][j];
		}
	}
	for(int i = 1; i <= n + n - 1; i++){
		for(int j = 1; j <= n + n - 1; j++){
			s[i][j] += s[i][j - 1];
		}
	}
	for(int i = 1; i <= n + n - 1; i++){
		for(int j = 1; j <= n + n - 1; j++){
			s[i][j] += s[i - 1][j];
		}
	}
	int ans = 0;
	int x1,y1,x2,y2;
	int len = n + n - 1;
	for(int i = 1; i <= n + n - 1; i++){
		for(int j = 1; j <= n + n - 1; j++){
			x1 = i - k;
			y1 = j - k;
			x2 = i + k;
			y2 = j + k;
			if(x1 < 1)x1 = 1;
			if(x2 < 1)x2 = 1;
			if(x1 > len)x1 = len;
			if(x2 > len)x2 = len;
			if(y1 < 1)y1 = 1;
			if(y2 < 1)y2 = 1;
			if(y1 > len)y1 = len;
			if(y2 > len)y2 = len; 
			ans = max(ans,getsum(x1,y1,x2,y2));
		}
	}
	cout<<ans<<endl;
}
int main(){
	sloved(); 
	return 0;
}

总结：是个好题，让我把二维前缀和捡起来了。以及坐标轴旋转45度的变换。(x,y) - > (x + y - 1, n - x + y).