题解：P13821 「Diligent-OI R2 A」蒹葭苍苍

dengzheli · 2025-08-23 18:02:26 · 题解

题目大意：给出一个图，图中有能走的和不能走的。要从第一行从左往右数的第一个能走的格子走的右往左数的第一个能走的格子，问最多能经过几个格子。

这道题...我用的是贪心和珅都要给我一个大拇指。

由于题目中没说不能到目的地时输出什么，于是我默认一定能到目的地好不严谨的说法，由于最后的地点在第n行，于是我就从第n行从下往上遍历，直到出现障碍物或到了第一行，之后ans就加上走的步数。因为向上或下走都可以，那就可以贪一下了。（具体请看代码：）

//这么丑的码风，你还敢抄代码吗？
#include <bits/stdc++.h>
using namespace std;
const int N = 105;//范围
const int X = 101;
int n, a[N][N], sy = 101, ey, ans;
int main() {
    scanf("%d", &n);
    for(int x, i = 1; i <= n; i++) {
        scanf("%d", &x);
        for(int j = 1; j <= x; j++) a[i][j] = 1;//此路通 
    }
    for(int j = 1; j < X; j++) 
    if(a[1][j]) {
        sy = j;//起点的y坐标 
        break;
    }
    for(int j = X - 1; j; j--) 
    if(a[n][j]) {
        ey = j;//起点的y坐标
        break;
    }
    for(int x, j = sy; j <= ey; j++) {
        x = n;
        while(a[x][j]) {
            x --;//移动 
            ans ++;//贪~心 
        }
    }
    printf("%d", ans);//输出答案
    return 0;
}