Disarmament of the Units 解答制作：牟田、黄 解答状況 • Submit: 3 • Accept: 1 • First Accept: 288分 問題概要 • 垂直水平方向に道路がある • 二軍の戦車がいて、 初期状態から目標状態へ →最短手数を答えよ • 戦車の移動には色々制約が – 他軍の戦車の射線× – 追い越せない – 曲がれない等々 最短移動例 目標 状態 目標 状態 ０手目 １手目 ２手目 ３手目 ４手目 ５手目 ６手目 ７手目 解法 • どうみても幅優先探索です 本当にありがとうございました • それではＴＬＥだったという方のために 片側探索→両側探索 • 終了状態が一意に 限られる • 探索木が幅広い Start Goal • 前からと後ろからの 両側探索が有利 集合はビット演算 • 戦車の位置を – (x1, y1), (x2, y2), (x3, y3) 座標表記 – 0001001001 ビット集合表記 • あと移動可能条件をビット集合にすると 色々な条件チェックが一発で可能 – ジャッジのコードでは遷移判定がアンド２回 次の状態作成がxor１回
© Copyright 2024 ExpyDoc
