Submission #60824295

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
<方針>
- 再帰的に探索を行う．ただし，倒す順番はヒープで最弱を指定する．
- 重複の無いように，スライムを既に倒したかどうか(`killed`)は管理する．
"""
import heapq
# 入力
H, W, XX = map(int, input().split())
P, Q = map(int, input().split())
SS = [list(map(int, input().split())) for _ in range(H)]
P -= 1
Q -= 1
killed = [[False]*W for _ in range(H)]
# 🛡️高橋くん🗡️の強さ
power = 0
# ヒープでスライムを倒していく．
## 強さ，縦インデックス，横インデックス
q = [[SS[P][Q], P, Q]]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

"""
<方針>
- 再帰的に探索を行う．ただし，倒す順番はヒープで最弱を指定する．
- 重複の無いように，スライムを既に倒したかどうか(`killed`)は管理する．
"""
import heapq
# 入力
H, W, XX = map(int, input().split())
P, Q = map(int, input().split())
SS = [list(map(int, input().split())) for _ in range(H)]
P -= 1
Q -= 1
killed = [[False]*W for _ in range(H)]

# 🛡️高橋くん🗡️の強さ
power = 0

# ヒープでスライムを倒していく．
## 強さ，縦インデックス，横インデックス
q = [[SS[P][Q], P, Q]]

# ヒープを回す
while q:
  # 強さ，縦インデックス，横インデックス
  p, y, x = heapq.heappop(q)
  
  # 既に倒されたかどうかを判定
  if killed[y][x]:
    continue
  else:
    killed[y][x] = True
  
  # 最初 or 倒せる条件のとき
  if power==0 or p<power/XX:
    # 🛡️高橋くん🗡を強化する
    power += p
    # 近傍を探索
    for (dy, dx) in [
      (0, 1), 
      (1, 0), 
      (0, -1), 
      (-1, 0), 
      ]:
      Y = y + dy
      X = x + dx
      # 枠内のとき
      if (0<=Y<H) and (0<=X<W):
        # TLE回避のために，自明な倒されたスライムは登録しない．
        if not killed[Y][X]:
          # そのスライムをヒープに登録する．
          heapq.heappush(q, [SS[Y][X], Y, X])
  # 近傍で最弱のスライムすら倒せない🛡️高橋くん🗡は引退してもらう
  else:
    break

# 出力
print(power)

Submission Info

Judge Result