自动搬运

查看原文

来自洛谷，原作者为

	chenyunting **

搬运于2025-08-24 23:13:44，当前版本为作者最后更新于2025-05-04 21:55:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

当三角形都是为图中这个样子的时候，如果顶点为[i-1][j]和顶点为[i][j-1]三角形的颜色相同，则顶点为[i][j]的三角形的腰为上面两个三角形中腰较短的加 1。

发现了这个规律，将每个朝向的三角形都算一遍最后取max就可以得到答案。

代码

#include <iostream>
#include <algorithm>
namespace noip {
typedef long long ll;
constexpr ll MAX_H_c = 1000;
ll h;
ll a[1+MAX_H_c][1+MAX_H_c];
ll zuoshang[1+MAX_H_c][1+MAX_H_c];
ll zuoxia[1+MAX_H_c][1+MAX_H_c];
ll youshang[1+MAX_H_c][1+MAX_H_c];
ll youxia[1+MAX_H_c][1+MAX_H_c];
void main() {
	std::cin >> h;
	for (ll i = 1; i <= h; i++)
		for (ll j = 1; j <= h; j++)
			std::cin >> a[i][j];
	
	for (ll i = 1; i <= h; i++)
		for (ll j = 1; j <= h; j++)
			zuoshang[i][j] = zuoxia[i][j] = youshang[i][j] = youxia[i][j] = 1;
	
	for (ll i = 2; i <= h; i++) 
		for (ll j = 2; j <= h; j++) 
			if (a[i][j] == a[i-1][j] && a[i][j] == a[i][j-1])
				zuoshang[i][j] = std::min(zuoshang[i-1][j], zuoshang[i][j-1])+1;
	
	for (ll i = 2; i <= h; i++)
		for (ll j = h-1; j >= 1; j--)
			if (a[i][j] == a[i-1][j] && a[i][j] == a[i][j+1])
				youshang[i][j] = std::min(youshang[i-1][j], youshang[i][j+1])+1;
			
	for (ll i = h-1; i >= 1; i--)
		for (ll j = 2; j <= h; j++)
			if (a[i][j] == a[i+1][j] && a[i][j] == a[i][j-1])
				zuoxia[i][j] = std::min(zuoxia[i+1][j], zuoxia[i][j-1])+1;
	
	for (ll i = h-1; i >= 1; i--)
		for (ll j = h-1; j >= 1; j--)
			if (a[i][j] == a[i+1][j] && a[i][j] == a[i][j+1])
				youxia[i][j] = std::min(youxia[i+1][j], youxia[i][j+1])+1;
	
	ll ans = 0;
	for (ll i = 1; i <= h; i++)	
		for (ll j = 1; j <= h; j++)	
			ans = std::max({ans, zuoshang[i][j], zuoxia[i][j], youshang[i][j], youxia[i][j]});
			
	std::cout << ans;
			
}
}

int main() {
	noip::main();
	return 0;
}