题解：CF1986B Matrix Stabilization

GCSG01 / 2024-08-23 / 原文

洛谷传送门

题意

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

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

本文同步发表于洛谷.