AOJ 2364 - Lucky Dip

Source

立命館大学プログラミング合宿 2012 (Day3)
AOJ 2364

問題概要

$R \times C$ 個のセルからなる $R$ 行 $C$ 列のフィールドが与えられる．
障害物のあるセル（$\verb|#|$）は最初は移動できない．
時間 $1$ から $N$ まで，各時間 $k$ に1つのセル $(x_k, y_k)$ が指定されて，そのセルに障害物があれば取り除かれる．
最初は左上のセルにいて，上下左右に移動できるとして（移動には時間はかからない），目的地のセル（$\verb|t|$ のセル）に移動できるようになる時間を求める問題．
最後まで移動不可能ならそれを指摘する．

$1 \leq R, C, N \leq 1000$

解法

まず時刻 $0$ の状態でBFSを行う．
そこで，各時間に開放されるセルにたどり着けるかどうかを逐次覚えていき，時刻を進めていく時，その時刻に開放されるセルに辿りつけているなら，そこを始点にBFSを再開するようにする．
他にも色々考えられて，答えに対する2分探索を行いそれぞれの時間で可能かどうかをBFSで愚直に調べる，Union Findを用いてセルをくっつけていく，上と似ているがダイクストラを用いて各セルに訪れることのできる最小時間を求めるなど．

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

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

Current time: 2024年04月20日05時30分40秒
Last modified: 2014年04月07日00時05分25秒 (by laycrs)
Tags: Competitive_Programming Aizu_Online_Judge Ritsumeikan_University_Programming_Camp
トップページに戻る

Logged in as: unknown user (not login)