题解：P12212 [蓝桥杯 2023 国 Python B] 最大阶梯

chenyunting · 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;
}