結果

問題 No.1949 足し算するだけのパズルゲーム(2)
ユーザー ThetaTheta
提出日時 2022-11-21 17:03:46
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,912 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 12,056 KB
実行使用メモリ 82,196 KB
最終ジャッジ日時 2023-10-22 07:26:10
合計ジャッジ時間 8,061 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge10
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
10,356 KB
testcase_01 AC 30 ms
10,356 KB
testcase_02 AC 30 ms
10,356 KB
testcase_03 AC 30 ms
10,360 KB
testcase_04 AC 30 ms
10,356 KB
testcase_05 AC 30 ms
10,356 KB
testcase_06 AC 30 ms
10,356 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, insort_left
from itertools import product


def get_neighbor(board: list[list[int]], current_y: int, current_x: int) -> list[tuple[int, int, int]]:
    neighbor = []
    try:
        neighbor.append(
            (board[current_y+1][current_x], current_y+1, current_x))
    except IndexError:
        pass

    if current_y > 0:
        neighbor.append(
            (board[current_y-1][current_x], current_y-1, current_x))

    try:
        neighbor.append(
            (board[current_y][current_x+1], current_y, current_x+1))
    except IndexError:
        pass

    if current_x > 0:
        neighbor.append(
            (board[current_y][current_x-1], current_y, current_x-1))

    return neighbor


def main():
    H, W, Y, X = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(H)]

    player_attack = board[Y-1][X-1]
    unvisited = set((board[y][x], y, x)
                    for y, x in product(range(H), range(W)))
    visited = set()
    unvisited.remove((board[Y-1][X-1], Y-1, X-1))
    visited.add((board[Y-1][X-1], Y-1, X-1))

    neighbor = get_neighbor(board, Y-1, X-1)
    neighbor.sort(reverse=True)

    for enemy in neighbor:
        unvisited.remove(enemy)

    while neighbor:
        weakest_enemy = neighbor.pop()
        if weakest_enemy[0] >= player_attack:
            print("No")
            return

        visited.add(weakest_enemy)

        player_attack += weakest_enemy[0]

        weakest_enemy_neighbor = get_neighbor(
            board, weakest_enemy[1], weakest_enemy[2])

        for enemy_near_weakest in weakest_enemy_neighbor:
            if (enemy_near_weakest in visited) or (enemy_near_weakest in neighbor):
                continue
            insort_left(neighbor, enemy_near_weakest,
                        key=lambda enemy: -1 * enemy[0])

    print("Yes")


if __name__ == "__main__":
    main()
0