题目题意:
在一个n×m的网格里,每个格子都有一定数量的敌人(可能为0),然后玉米加农炮的攻击范围是曼哈顿距离不超过2,即横向和纵向各扩展两格的十字区域以及四个角,敌人将会有q次增援,每一次增援是在方格(x,y),增加z个敌人,要求我们在每一次增援后,找到可以消灭最大敌人的方格坐标。
题目分析:
题目要求我们在每一次增援后,找到那个消灭最多的格子。
那么我们就可以先在增援之前就把每一个格子能攻击到的敌人给记录下来,并且记录未增援时可以攻击到最多敌人的位置以及数量。
在每一次增援时我们就可以直接计算增援的这个格子所能影响到的加农炮,并将其加上z个敌人,与此同时,我们就可以去比较将被加过的值与最大值相比较,如果大于了最大值我们就更新最大值,以及所对应的点,这样便能得到答案。
根据该思路,我们就可以写代码了:
#include<bits/stdc++.h>
using namespace std;
int dx[]={0,1,2,0,0,-1,-2,0,0,1,-1,1,-1}; //定义偏移数组
int dy[]={0,0,0,1,2,0,0,-1,-2,1,-1,-1,1};
int a[520][520]; //用来存初始时每个点的人数
long long b[520][520]; //用来记录每个点加农炮所能攻击到的人数
void solve(){
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
long long maxx=0,ans_x=0,ans_y=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<13;k++){
int tx=i+dx[k];
int ty=j+dy[k];
if(tx>=1 && tx<=n && ty>=1 && ty<=m){
b[i][j]+=a[tx][ty]; //记录在符合题意且合法的条件下,加农炮所能攻击攻击的的人数
}
if(b[i][j]>maxx){
maxx=b[i][j]; //记录最大攻击数以及所对应的坐标
ans_x=i,ans_y=j;
}
}
}
}
for(int i=1;i<=q;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]+=z;
for(int k=0;k<13;k++){ //更新增援后所能影响到的加农炮的攻击人数
int tx=x+dx[k];
int ty=y+dy[k];
if(tx>=1 && tx<=n && ty>=1 && ty<=m){
b[tx][ty]+=z;
if(b[tx][ty]>maxx){
maxx=b[tx][ty]; //更新最大攻击数以及所对应的坐标
ans_x=tx,ans_y=ty;
}
}
}
cout<<ans_x<<" "<<ans_y<<endl; //输出答案
}
}
int main(){
int t=1;
while(t--){
solve();
}
}

京公网安备 11010502036488号