蟻本の練習問題埋め2-1(1)
DFS&BFS
POJ 1979 : Red and Black
AOJ 0118 : Property Distribution
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118
多分やるだけ
AOJ 0033 : Ball
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
多分やるだけ
AOJ 0558 : Cheese
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558
多分やるだけ
POJ 3009 : Curling 2.0
POJ 3669 : Meteor Shower
http://poj.org/problem?id=3669
問題
雷から逃げる。
M個の雷が落ちるセルの座標と時間が与えれられる。
雷が落ちると、落ちたセルと4近傍が破壊される。
破壊されたセルにはもはや位置することができない。
時間0で原点にいるので、安全な場所まで移動する最短時間を求めよ。
移動できない場合は-1。
ただし、4近傍に時間1で移動でき、第1象限のみ移動できる。
制約
M <= 50000
0 <= 雷が落ちる座標x,y <= 300
雷が落ちる時間 <= 1000
解法
最初に、各セルに対して破壊される時間をO(M)で配列に入れておく。
このとき破壊されないセルに対してはINFとしておく。
その後、幅優先でまだ破壊されていない場所を移動していく。
破壊される時間がINFな場所にたどり着いたら終わり。
1度見たセルは見ない。
AOJ 0121 : Seven Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121
多分やるだけ
