[Algorithm] BaekJoon : 17837. 新しいゲーム2 by Python

[問題のショートカット]https://www.acmicpc.net/problem/17837

📌問題の説明

ヒョンは周囲を見ながら碁盤とマレーで新しいゲームを作ることにした.新しいゲームサイズはN×Nチェス盤で行い、使用する馬の個数はK個です.馬は原版で、1匹はすぐに別の馬を置くことができます.チェス盤の各コマは白、赤、青の1つに塗られている.
ゲームは碁盤にK頭馬を乗せてから始まります.馬は1番からK番まで番号があり、移動方向も予め決まっています.移動方向は、上、下、左、右の4つのいずれかです.
一回のターンは1番馬からK番馬の順に移動します.1頭の馬が移動すると、上の馬も一緒に移動します.馬の移動方向の欄によって、馬の移動は以下のように異なります.回転中に4つ以上の馬を積んだ瞬間、ゲームは終了.

A号馬が移動する車両

ホワイトの場合は、セルに移動します.移動するセルにすでに馬がいる場合は、A番馬を一番上に置きます.

A番馬の上に他の馬がいるとA番馬と上のすべての馬が移動します.

例えば、

は、A、B、Cに積まれており、移動するセルにD、Eがあれば、A番馬が移動するとD、E、A、B、Cとなる.

赤の場合は、移動後にA番馬と上のすべての馬の積み重ね順を逆さまにします.

A,B,Cは移動し,移動する格子に馬がなければC,B,Aとなる.

A,D,F,G移動するセルにE,C,B,G,F,D,Aがある場合.

ブルーの場合、A番馬の移動方向が反対になり、1マス移動します.方向反転後に移動するセルが青の場合は、移動せずに静止します.

チェス盤を離脱した場合は青と同じである.

サイズ4×4人のチェス盤には馬が4頭います.

第1ラウンドは以下のように行われる.

第2ラウンドは以下のように行われる.

碁盤の大きさ,馬の位置,移動方向ともにタイミングを与え,ゲーム終了時のラウンド番号を求める.
入力
1行目は碁盤サイズN,馬の個数Kを与える.2行目からN行はチェス盤の情報を与える.チェスボードの情報は整数で構成され、各整数はセルの色を表します.0は白、1は赤、2は青です.
次のK行では、馬の情報は1番馬から順に与えられます.馬の情報は、行、列の番号、移動方向の3つの整数で構成されています.行と列の番号は1から、移動方向は4以下、1から順に→、←、↑、↓です.
同じ欄に馬が2つ以上ある場合は入力できません.
しゅつりょく
ゲーム終了時のラウンド番号を出力します.この値が1000より大きい場合、またはゲームが絶対に終了しない場合は、-1を出力します.
制限

4 ≤ N ≤ 12

4 ≤ K ≤ 10

💡 問題を解く

与えられた問題をそのまま体現すれば、問題を解決することができる.
問題の鍵はチェス盤の馬が移動するときに他のすぐ下にいることができるので、「どのような資料構造を使って馬の移動を表現するか」です.
碁盤の大きさは最大12×12、メモリは512 MBに制限され、馬の位置と碁盤上の移動を別々に行う.
馬の位置はディックの棒で「馬番号:座標」と入力した値です.
チェス盤の移動は3次元配列を採用しており,特定の座標に複数の馬を積むと,その座標配列に入った馬の番号が順次追加される.
step 1)
変数の宣言
location:チェスボード上を移動する3 D配列
馬:馬の位置を示すディック・シャナリー-「馬番号:座標」
ゲーム進行時の「ラウンド」値の変数
step 2)
すべての馬を順番に1回移動すると1ラウンドになるので、繰り返し文で1ラウンドを終えて+1と答えます.
馬の移動のために,解関数を確立した.
馬の番号で移動する座標を計算する
新しい座標がチェス盤の範囲に入ると、2つのケースに分けられます.

移動するセルは白で、赤の場合は

です.

移動するセルが青の場合

新しい座標がチェス盤の範囲に入っていない場合

のような青色の場合、blue関数が実行されます.

白と赤をwhite red関数に組み合わせたのは、赤のセルに移動すると話の順序が変わるだけで、他の操作は白と同じだからです.
step 3)
移動するセルが白、赤の場合→white red関数
locationで移動する馬の番号を検索します.(後続馬の取得に使用)
見つかったら、後ろの馬を滑車で移動する欄にマージします.

ホワイトの場合は、順番に合わせます.

赤の場合、前後順に交互にマージされます.

移動後は移動前の格子に滑車で移動した馬を消滅させる.
step 4)
馬を動かし、4つ以上の馬を積み上げ、直ちに進行を止める.→is finish関数
移動座標(nr,nc)の配列長が4より大きい場合はresult出力後exit()関数を使用してプログラムを終了します.
4以上でなければ、新しく移った馬の座標を更新します.
step 5)
solve関数で移動する座標がチェス盤の範囲を超えたり、青になったりする場合はblue関数を実行します.
blue関数はまず方向を変えた.
左(1)、右(2)/上(3)、下(4)が入れ替わるので、奇数、+1偶数であれば-1をして向きを変えます.
変化する方向に1コマ移動します.
移動するセルが白または赤の場合はwhite red関数を実行します.
移動するセルがチェス盤か青いのであれば方向を変えるだけでいいのですが、ブルー関数は方向を変えているので、続ける内容はありません.
コードは次のとおりです.

import sys
dir = [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0)]
N, K = map(int, input().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def is_finish(nr, nc):
    if len(location[nr][nc]) >= 4:
        print(answer)
        exit()

def white_red(r, c, nr, nc, num, color):
    for idx in range(len(location[r][c])):
        if location[r][c][idx] == num:
            if color == "white": location[nr][nc] += location[r][c][idx:]
            else: location[nr][nc] += location[r][c][idx:][::-1]
            location[r][c] = location[r][c][:idx]
            break
    is_finish(nr, nc) # 4개의 말이 쌓였는지 확인
    for horse in location[nr][nc]:
        horses[horse][0], horses[horse][1] = nr, nc

def blue(r, c, d, num):
    if d % 2: d += 1
    else: d -= 1
    horses[num][2] = d
    nr = r + dir[d][0]
    nc = c + dir[d][1]
    if 0 <= nr < N and 0 <= nc < N:
        if not matrix[nr][nc]: white_red(r, c, nr, nc, num, "white") # 흰색
        elif matrix[nr][nc] == 1: white_red(r, c, nr, nc, num, "red") # 빨간색

def solve(num):
    r, c, d = horses[num]
    nr = r + dir[d][0]
    nc = c + dir[d][1]
    if 0 <= nr < N and 0 <= nc < N:
        if not matrix[nr][nc]: # 흰색
            white_red(r, c, nr, nc, num, "white")
        elif matrix[nr][nc] == 1: # 빨간색
            white_red(r, c, nr, nc, num, "red")
        else: # 파란색
            blue(r, c, d, num)
    else:
        blue(r, c, d, num)

location = [[[] for _ in range(N)] for _ in range(N)]
horses = dict()
for idx in range(K):
    r, c, d = map(int, input().split())
    location[r-1][c-1].append(idx)
    horses[idx] = [r-1, c-1, d]

answer = 1
while answer < 1000:
    for num in range(K):
        solve(num)
    answer += 1
print(-1)