UVa 12845 - The Jolly Friar's Puzzle

Source

Second UVa regional warmup(20141101)
UVa 12845

問題概要

$4 \times 4$ のマス目のうちに $10$ 個のセルに石が置いてある.
$1$ 回の手順では,石が置いてあるセルから石を取り除き,石の置いていない任意のセルに石を置くことができる.
縦,横,斜めのラインで,石の数が $0$ でない偶数個のラインが $16$ ライン(最大値)であるような状況にしたい.
ここで,斜めのラインは対角線以外の,セルが $1$ ~ $3$ 個しかないようなラインも考える.
最小手数を求める問題.

解法

最初に $2^{16}$ パターンの盤面を全て作り,それらがゴールの状態になるかどうかを調べる.
後は,各ケースごとに,各ゴールの状態に一致していない石の数を調べて最小値を取れば良い.
それはビットの数を数えることで高速に可能だけど,そこまでは多分必要ない(ゴールの状態となる盤面の数はかなり少ない).

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

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


Current time: 2017年07月24日15時50分26秒
Last modified: 2014年11月08日19時32分26秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20141101_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: