結果

問題 No.1949 足し算するだけのパズルゲーム(2)
コンテスト
ユーザー Theta
提出日時 2022-11-21 17:10:46
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,100 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 53,236 KB
最終ジャッジ日時 2024-09-22 08:37:34
合計ジャッジ時間 5,354 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left, insort_left
from collections import deque
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 = deque(neighbor)

    for enemy in neighbor:
        unvisited.remove(enemy)

    while neighbor:
        for _ in range(len(neighbor)):
            neighbor.rotate(1)
            if neighbor[0][0] < player_attack:
                weak_enemy = neighbor.popleft()
                break
        else:
            print("No")
            return
        # weakest_enemy = neighbor.pop()
        # if weakest_enemy[0] >= player_attack:
        #     print("No")
        #     return

        visited.add(weak_enemy)

        player_attack += weak_enemy[0]

        weak_enemy_neighbor = get_neighbor(
            board, weak_enemy[1], weak_enemy[2])

        for enemy_near_weak in weak_enemy_neighbor:
            if (enemy_near_weak in visited) or (enemy_near_weak in neighbor):
                continue
            neighbor.append(enemy_near_weak)

    print("Yes")


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