2023_하_P_1_L14

루돌프의 반란

Simulation

평균 : 180'

---

sol : -

• 수행 시간 : -
• 메모리 : -

New Skills

• 연쇄 이동 -> 재귀 함수 호출 : 약점 보완 필요

MAX_DIS = 6000

n, m, p, c, d = map(int, input().split())
r = list(map(int, input().split()))
santa_pos = [list(map(int, input().split())) for _ in range(p)]
# score, alive, stun
santa_stat = [[0, True, 0] for _ in range(p + 1)]
santa_map = [
    [0 for _ in range(n + 1)]
    for _ in range(n + 1)
]

santa_pos.sort(key=lambda x: x[0])

dss = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]


for pos in santa_pos:
    santa_map[pos[1]][pos[2]] = pos[0]

def debug(board):
    for i in range(n):
        for j in range(n):
            if r[0] == i and r[1] == j:
                print(-1, end=" ")
            else:
                print(santa_map[i][j], end=" ")
        print()

# print 있음
def check_game():
    for s in santa_stat[1:]:
        if s[1]:
            return False
    return True


def get_distance(a, b):
    return pow((a[0] - b[0]), 2) + pow((a[1] - b[1]), 2)


def inbound(r, c):
    if 0 < r <= n and 0 < c <= n:
        return True
    return False

# [5, 1, 3]
def get_nearest_santa():
    min_dis = MAX_DIS
    min_pos = tuple((-1, -1))
    min_santa = 0

    for indices, stat in zip(santa_pos, santa_stat[1:]):
        if not stat[1]:
            continue
        c_pos = tuple((indices[1], indices[2]))
        c_dis = get_distance(r, indices[1:])
        if min_dis == c_dis:
            if min_pos < c_pos:
                min_pos = c_pos
                min_santa = indices[0]
        if min_dis > c_dis:
            min_dis = c_dis
            min_pos = tuple((indices[1], indices[2]))
            min_santa = indices[0]

    return [min_santa] + list(min_pos)

# [5, 1, 3]
def r_move(tgt):
    global r
    min_dis = MAX_DIS
    next_pos = [-1, -1]
    c_ds = []

    for ds in dss:
        nr, nc = r[0] + ds[0], r[1] + ds[1]
        if inbound(nr, nc):
            c_dis = get_distance([nr, nc], tgt[1:])
            if min_dis > c_dis:
                min_dis = c_dis
                next_pos = [nr, nc]
                c_ds = ds

    r = next_pos
    if santa_map[r[0]][r[1]] == tgt[0]:
        crush(tgt, c_ds, c)

# [5, 1, 3]
def eliminate(tgt):
    print(tgt[0], 'eliminated')
    santa_map[tgt[1]][tgt[2]] = 0
    santa_pos[tgt[0] - 1][1], santa_pos[tgt[0] - 1][2] = -1, -1
    santa_stat[tgt[0]][1] = False
    return


def crush(tgt, ds, power):
    global finished
    ni, nj = tgt[1] + ds[0] * power, tgt[2] + ds[1] * power

    if not inbound(ni, nj):
        eliminate(tgt)

    else:
        # k턴 기절시 k, k+1턴 기절
        print('at ', turn, 'turn,', tgt[0],' crushed')
        santa_stat[tgt[0]][2] = turn + 2
        # map 갱신 전 상호작용 체크
        next_one = santa_map[ni][nj]
        if next_one != 0:
            santa_map[ni][nj] = tgt[0]
            interaction(next_one, ds)

        # map 갱신
        santa_map[tgt[1]][tgt[2]] = 0
        santa_map[ni][nj] = tgt[0]
        santa_pos[tgt[0] - 1][1], santa_pos[tgt[0] - 1][2] = ni, nj

    santa_stat[tgt[0]][0] += power
    return


# 1 대입
def interaction(santa, ds):
    print('interacted')
    print(santa)
    cs = santa
    # 1 위치
    ci, cj = santa_pos[cs - 1][1], santa_pos[cs - 1][2]
    # 1 다음 위치 (6의 위치)
    while santa_map[ci + ds[0]][cj + ds[1]] != 0:
        ci, cj = santa_pos[cs - 1][1], santa_pos[cs - 1][2]
        ni, nj = santa_pos[cs - 1][1] + ds[0], santa_pos[cs - 1][2] + ds[1]
        if not inbound(ni, nj):
            eliminate(santa_pos[cs - 1])
            return
        else:
            next_one = santa_map[ni][nj]
            # map update
            santa_map[ci][cj] = 0
            santa_map[ni][nj] = cs
            # pos update
            santa_pos[cs - 1][1], santa_pos[cs - 1][2] = ni, nj
            if next_one != 0:
                cs = next_one
            else:
                interact = False
    santa_map[ci + ds[0]][cj + ds[1]] = santa


def s_move():
    for indices, stat in zip(santa_pos, santa_stat[1:]):
        # 아웃된 산타
        if not stat[1]:
            continue
        # 기절한 산타
        if stat[2] > turn:
            continue
        if stat[2] == turn:
            stat[2] = 0

        min_dis = get_distance(r, [indices[1], indices[2]])
        min_pos = [-1, -1]
        update = False
        c_ds = []
        for ds in dss[::2]:
            ni, nj = indices[1] + ds[0], indices[2] + ds[1]
            if inbound(ni, nj) and santa_map[ni][nj] == 0:
                cur_dis = get_distance(r, [ni, nj])
                if min_dis > cur_dis:
                    update = True
                    min_pos = [ni, nj]
                    min_dis = cur_dis
                    c_ds = ds

        if update:
            # 산타 맵 업데이트
            santa_map[indices[1]][indices[2]] = 0
            santa_map[min_pos[0]][min_pos[1]] = indices[0]
            # 산타 위치 업데이트
            indices[1], indices[2] = min_pos[0], min_pos[1]

            if r == indices[1:]:
                crush(indices, [c_ds[0] * -1, c_ds[1] * -1], d)


def add_score():
    for santa in santa_stat[1:]:
        if santa[1]:
            santa[0] += 1

finished = False
turn = 1
def simulate():
    global finished, turn
    while not finished and turn <= m:
        print(turn, "turn")
        target = get_nearest_santa()

        print('r', r, ': target', target)
        print('score: ', santa_stat[1:])
        print('idx: ', santa_pos)
        debug(santa_map)

        r_move(target)
        print('r after', r)

        s_move()
        print('santa after')
        debug(santa_map)

        add_score()

        finished = check_game()
        print('after score', santa_stat[1:])
        print('after indices', santa_pos)
        print()
        turn += 1

########################################################
simulate()
for s in santa_stat[1:]:
    print(s[0], end=" ")