SPOJ 25 - Pouring water [POUR1]

Source

SPOJ 25 [POUR1]

問題概要

容量 $A$ の容器と,容量 $B$ の容器があり,最初は両方とも空.
以下の行動1~3が行える時,最短で何手で,どちらか片方の容器にちょうど $C$ だけの水が入っている状態にできるかを求める問題.
不可能ならば,それを指摘する.

  1. 片方の容器に入っている水を全部捨てる
  2. 片方の容器に満杯になるまで水を入れる
  3. 片方の容器から片方の容器に,水がなくなるか,もう入らない状態になるまで水を入れる

解法

BFSする.
必ずどちらかの容器は,空か満杯なので,どちらの容器が空または満杯か,という情報と,残りの容器にいくらの水が入っているかを状態にする.
状態数は $4 \max(A,B)$ 程度.

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

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


Current time: 2017年09月21日05時07分19秒
Last modified: 2014年04月03日16時13分26秒 (by laycrs)
Tags: Competitive_Programming Sphere_Online_Judge SPOJ_Classical Breadth_First_Search
トップページに戻る

Logged in as: unknown user (not login)

ログイン: