UVa 12847 - Who Will Get the Nomination?

Source

Second UVa regional warmup(20141101)
UVa 12847

問題概要

$5 \times 5$ のマス目に最大 $9$ 個のコマが置いてある盤面が与えられる.
$1$ 回の操作では $1$ つのコマを選び,上下左右に $1$ マス移動させるか,上下左右にあるコマを $1$ 個だけ飛び越えて,飛び越したコマを消すことができる.
コマを $1$ つだけマス目の真ん中のマスにあるような状態にするための最小手数を求める問題.

解法

各テストケースに対して答えを簡単に求まるようにするために,終点からBFSする.
つまり,真ん中に $1$ つのコマがある状態から,上下左右に $1$ マス移動させるか,上下左右に $2$ マス移動して移動した始点と終点の間にコマを追加するという風に逆に操作していく.
コマの数が $10$ 個以上になる状態には遷移しない.
ただし微妙に制限時間に間に合わないので,上下左右の鏡像反転や,90度回転して一致する盤面は同じとみなすとか,
状態遷移をビット演算を用いて高速化などしておけば間に合う.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年07月25日05時38分28秒
Last modified: 2014年11月08日19時37分24秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20141101_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: