[BOJ]17825-ゲーム

34520 ワード
boj インプリメンテーション BFS/DFS サムスン電子 アルゴリズム#アルゴリズム# テキストリンク

質問リンク


17825-ゲームを投げる

問題の説明


次のゲームではサイコロを10回投げて馬を動かします.
  • 初期、4つはすべて開始格の中で、
  • のゲームボードの矢印に従ってしか移動できません->青い格子から移動し、青い格子から移動し、赤い矢印から移動します.
  • に到着すると、サイコロの数字にかかわらず、
    • の移動が完了します.
  • ゲームは10ラウンドからなる.ラウンドごとに1～5の5面体サイコロを転がし、格に届かない馬を1つ選び、サイコロの数字に従って移動します.
  • 馬が移動を終えた後、他の馬がいるとその馬は選べません.->
  • 馬が移動を終えるたびに、格子の数字が点数に追加されます.

    • 問題を解く


    そのゲームボードをどのように保存するかが重要な問題のようです.私もそこで長い間悩んでいましたが、、、

    ゲームボードを保存


    ゲーム版はBoard DickShowneryに保存されており、以下のようになっています.board[i] = [(score, next)]:i 1番目の欄の点数はscoreで、矢印が指す次の欄はnextです.horses[i]:i 2頭目の馬がいる欄番号
    board = defaultdict()
for i in range(21):
    board[i] = [(i*2, i+1)]
board[21] = [(0, -1)] # 도착칸

board[5].append((10, 22))
board[22] = [(13, 23)]
board[23] = [(16, 24)]
board[24] = [(19, 25)]

board[10].append((20, 29)) 
board[29] = [(22, 30)]
board[30] = [(24, 25)]

board[15].append((30, 28))
board[28] = [(28, 27)]
board[27] = [(27, 26)]
board[26] = [(26, 25)]

board[25] = [(25, 31)]
board[31] = [(30, 32)]
board[32] = [(35, 20)]

    dfs


    dfsを用いてすべての状況を探索した.
    def dfs(dice, score):
    global answer
    if len(dice) == 0:
        # 주사위 10번에 대해서 다 돌았으면
        answer = max(answer, score)
        return
    
    for h in range(4):
        if horses[h] != 21:
            x = horses[h]
            # 해당 말 dice[0]만큼 이동 후 얻은 점수 계산
            score_this_turn = move(dice[0], h)
            if score_this_turn < 0:
                continue
            dfs(dice[1:], score+score_this_turn)
            # 이전 상태로 돌리기
            horses[h] = x

    馬の移動


    馬の移動部分は以下の通りである.
    def move(moves, h):
    # h번째말 moves번 이동시키기
    x = horses[h]
    next_pos = 0
    flag = False
    
    # 처음 1칸 이동
    if x in [5,10,15]:
        next_pos = board[x][1][1]
    else:
        next_pos = board[x][0][1]
    
    # 이동한 칸이 도착칸이면
    if next_pos == 21:
        horses[h] = next_pos
        flag = True
    else:
        # moves-1칸 이동
        for i in range(moves-1):
            next_pos = board[next_pos][0][1]
            if next_pos == 21:
                # 이동하다가 도착칸을 만나면
                horses[h] = next_pos
                flag = True
                break
    
    # 현재 말의 상태 갱신 -> 도착한 칸에 다른 말 있는지 검사
    if flag != True:
        for i in range(len(horses)):
            if i != h:
                if horses[i] == next_pos:
                    return -1
        horses[h] = next_pos
                    
    return board[horses[h]][0][0]

    完全なコード

    import sys
from collections import defaultdict
input = sys.stdin.readline

dice = list(map(int, input().split()))
# board[i]:[(score, next)] -> i번째 칸은 (score 점수, 다음 칸)
board = defaultdict()
for i in range(21):
    board[i] = [(i*2, i+1)]
board[21] = [(0, -1)] # 도착칸

board[5].append((10, 22))
board[22] = [(13, 23)]
board[23] = [(16, 24)]
board[24] = [(19, 25)]

board[10].append((20, 29)) 
board[29] = [(22, 30)]
board[30] = [(24, 25)]

board[15].append((30, 28))
board[28] = [(28, 27)]
board[27] = [(27, 26)]
board[26] = [(26, 25)]

board[25] = [(25, 31)]
board[31] = [(30, 32)]
board[32] = [(35, 20)]

horses = [0 for _ in range(4)]
answer = 0

def move(moves, h):
    # h번째말 moves번 이동시키기
    x = horses[h]
    next_pos = 0
    flag = False
    
    # 처음 1칸 이동
    if x in [5,10,15]:
        next_pos = board[x][1][1]
    else:
        next_pos = board[x][0][1]
    
    # 이동한 칸이 도착칸이면
    if next_pos == 21:
        horses[h] = next_pos
        flag = True
    else:
        # moves-1칸 이동
        for i in range(moves-1):
            next_pos = board[next_pos][0][1]
            if next_pos == 21:
                # 이동하다가 도착칸을 만나면
                horses[h] = next_pos
                flag = True
                break
    
    # 현재 말의 상태 갱신 -> 도착한 칸에 다른 말 있는지 검사
    if flag != True:
        for i in range(len(horses)):
            if i != h:
                if horses[i] == next_pos:
                    return -1
        horses[h] = next_pos
                    
    return board[horses[h]][0][0]

def dfs(dice, score):
    global answer
    if len(dice) == 0:
        # 주사위 10번에 대해서 다 돌았으면
        answer = max(answer, score)
        return
    
    for h in range(4):
        if horses[h] != 21:
            x = horses[h]
            # 해당 말 dice[0]만큼 이동 후 얻은 점수 계산
            score_this_turn = move(dice[0], h)
            if score_this_turn < 0:
                continue
            dfs(dice[1:], score+score_this_turn)
            # 이전 상태로 돌리기
            horses[h] = x

dfs(dice, 0)
print(answer)

    所要時間


    4時間最も解決しにくい実施難題は、
    馬が行ってしまったので,ほかの馬はもう担げない.
    これがどういう意味なのか理解できないので、別のブログを参考にしましたが、結局このラウンドで、この言葉は私を通過させた意味です.
    linux 5.14のlistenの実装を記録します
    PCATADAの紹介~🎉