题目大意
给定一个矩阵，每次选择一个比它所有“邻居”都大的项，不断减一直到它不满足以上条件，求修改完后的矩阵。
“邻居”的定义是左右相邻或上下相邻，不包括对角线的情况。
解题思路
我们首先要明白一点，别看题目中讲要找坐标小的先修改，实际上修改顺序是不重要的。
而要明白这一点我们又要明白另一点，那就是所有被选中的项都互不是“邻居”。这一点很好想，假设有两个项 \(a_{i,j}\) 和 \(a_{i+1,j}\)，它们互为邻居。你先修改 \(a_{i,j}\)，修改完成后 \(a_{i,j}\) 应该等于它所有“邻居”中的最大值，而 \(a_{i+1,j}\) 也是它的邻居，那么自然 \(a_{i+1,j}\) 就不会比 \(a_{i,j}\) 要大，不会被选中。
明白了这一点，刚才那一点也就好想了，因为不同被选中的项是互不干扰的，它们的“邻居”自始至终都不会变，先修改哪一个都无所谓。
那么我们从 \(a_{1,1}\) 依次遍历到 \(a_{n,m}\)，看 \(a_{i,j}\) 是否满足比所有“邻居”大的条件，如果是，那么就把 \(a_{i,j}\) 直接修改为所有“邻居”中的最大值。全部修改完成后就是所求矩阵了。
代码实现
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,m,maxx;
int a[110][110];
int main(){scanf("%d",&t);while(t--){memset(a,0,sizeof(a));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){maxx=0;maxx=max(maxx,max(a[i+1][j],max(a[i-1][j],max(a[i][j+1],a[i][j-1]))));if(maxx<a[i][j]) a[i][j]=maxx;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d ",a[i][j]);}printf("\n");}}return 0;
}
时间复杂度 \(O(nm)\)，题目中说所有 \(n \times m\) 的和不会超过 \(2 \times 10^5\)，稳过。
注意事项
- 如果不特判边界的话记得每次清空矩阵 \(a\)，否则在遍历到 \(a\) 的边界时会受到上一次输入的干扰。