题解：CF1986B Matrix Stabilization

洛谷传送门

题意

一个 \(n\times m\) 的矩阵，依次进行以下操作：

1. 从 \((1,1)\) 开始遍历矩阵，找到最小的 \((i,j)\) 满足 \(a{i,j}\) 的值严格大于其所有相邻（四联通）单元格的值，如果没有则退出
2. 将 1 操作找到的 \(a_{i,j}-1\)
3. 返回 1 操作

求最后的矩阵。

思路

模拟，我们按照题目所说，从 \((1,1)\) 到 \((n,m)\) 依次枚举 \(a_{i,j}\)，如果 \(a_{i,j}\) 是周围四个中最大的一个，进行操作。
操作：如果当前的数减 \(1\) 后不满足条件，那么就不用再进行操作，如果减 \(1\) 后任满足条件，那么它一定会减小至周围四个数的最大值，至此，输出即可。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[105][105];
void check(int x,int y)
{
	int A,B,C,D;
	A=B=C=D=0;
	if(x-1>=1)A=a[x-1][y];
	if(x+1<=n)B=a[x+1][y];
	if(y-1>=1)C=a[x][y-1];
	if(y+1<=m)D=a[x][y+1];
	int s=a[x][y];
	if(s<A||s<B||s<C||s<D)return;
	a[x][y]=max(A,max(B,max(C,D)));
	return ;
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>a[i][j];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				check(i,j);
		for(int i=1;i<=n;i++,cout<<"\n")
			for(int j=1;j<=m;j++)
				cout<<a[i][j]<<" ";
	}
	return 0;
}

本文同步发表于 洛谷.