题意: 现有n*m的矩阵,将q次对单元格增加,求每次增加之后的曼哈顿距离不超过2的所有方格之和的最大值在哪个方格?

知识点: 暴力

思路: 我们可以先暴力枚举出每一个方格曼哈顿距离不超过2的所有方格之和,接着在枚举的过程中顺手记录下其中和最大的方格下标。接着对于每个q来说,他增加的那个z也只有曼哈顿距离不超过2的单元格才会受到影响,只要直接预处理的和数组把曼哈顿距离不超过2的单元格和全部加上z就可以了。然后加的过程中再拿之前记录的最大值下标比较,并记录最新的和最大下标即可。

参考代码:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
using namespace std;
int dx[12]={0,0,1,1,2,0,0,1,-1,-1,-2,-1};
int dy[12]={1,2,1,0,0,-1,-2,-1,-1,0,0,1};
bool judg(int x1,int y1,int n,int m)
{
	return (x1>=0&&x1<n&&y1>=0&&y1<m);
}
int main()
{
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
	int n,m,q;
	cin >> n >> m >> q;
	vector<vector<ll>> a(n,vector<ll>(m));
	vector<vector<ll>> w(n,vector<ll>(m,0));
	ll maxx=0,maxy=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin >> a[i][j];
	w=a;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++){
			for(int k=0;k<12;k++){
				int nex=i+dx[k],ney=j+dy[k];
				if(judg(nex,ney,n,m))
					w[i][j]+=a[nex][ney];
			}
			if(w[maxx][maxy]<w[i][j])
				maxx=i,maxy=j;
		}
	while(q--){
		int x,y,z;
		cin >> x >> y >> z;
		w[x-1][y-1]+=z;
		if(w[maxx][maxy]<w[x-1][y-1])
			maxx=x-1,maxy=y-1;
		for(int i=0;i<12;i++){
			int nex=(x-1)+dx[i],ney=(y-1)+dy[i];
			if(judg(nex,ney,n,m)){
				w[nex][ney]+=z;
				if(w[maxx][maxy]<w[nex][ney])
					maxx=nex,maxy=ney;
			}
		}
		cout << maxx+1 << ' ' << maxy+1 << endl;
	}
	return 0;
}