[白俊]14719-雨水(Python)

6678 ワード
boj アルゴリズム#アルゴリズム# テキストリンク
質問リンク

質問する


2次元の世界には積み木がいっぱい積まれている.雨が降ると、積み木の間に雨が溜まります.
雨がひどく降った.水たまりの雨水の総量はいくらですか?

アルゴリズム#アルゴリズム#

  • 実施
  • シミュレーション

    • 入力


    第1行は、2次元世界の長手方向長さHおよび2次元世界の横方向長さWを与える.
    (1 ≤ H, W ≤ 500)
    2行目には、ブロックの積み上げ高さを表す0以下の整数が含まれます.
    2次元世界の最も左側の位置から順にW個を与える.
    したがって、ブロック内部に空きスペースがあることはできません.
    また,二次元世界の底は常に塞がれていると仮定できる.

    しゅつりょく


    2 Dワールドでは、1グリッドの容量は1です.積水の総量を出力する.
    雨が全く積もらなければ、0を出力します.

    入力例

    4 8
3 1 2 3 4 1 1 2

    出力例

    5

    I/O例説明



    に答える


    2 Dリストは、
  • によって与えられたHおよびWを使用して生成される.
    • 生成
  • のリストにブロックを入れます.
  • すべての座標を巡回し、座標の左右にブロックがあるかどうかを決定し、結果値に1を追加します.

    コード#コード#

    import sys

input = sys.stdin.readline

H, W = map(int, input().split())
blocks = list(map(int, input().split()))

# 2차원 세계 생성 (블록은 True, 빈공간은 False)
world = [[False for _ in range(W)] for _ in range(H)]
for w in range(W):
    for h in range(H):
        if h >= H - blocks[w]:
            world[h][w] = True

rain = 0

# 모든 좌표를 순회
# 좌표값이 False 이고 좌우에 True가 하나라도 있으면 1추가
# index(True)가 오류날 것을 대비해 try 구문 사용
for i in range(H):
    for j in range(W):
        try:
            if world[i][j] == False and world[i].index(True) < j < (W - 1) - world[i][::-1].index(True):
                rain += 1
        except:
            continue
print(rain)
    • 応答のアルゴリズムの方面(diffing、Heristic)
    Try & Catch