手首のリハビリ替わりにPKU.まだまだかくのしんどい.
概要
与えられた迷路のどこにいても脱出できる最短の方向リストを求めよ.
壁の方向に進もうとした場合はその場にとどまる.複数解ある場合はどれを出力してもよい.
その昔に友人がヒューリスティックで解いたよーとかいってて,どうやって解くんだろうと思っていたけど,病院に持っていったプリントにこの問題があったので考えてみた.この問題は64マスなので,set
解法
最初に出口と壁以外の全てのところに人がいると仮定して一歩ずつ動かして行く.幅優先だと余裕でTLEなので,ヒューリスティックに解く.ヒューリスティックの値は,『出口から一番遠い人の距離』(簡単だけど反転).状態をビットで持ったせいか結構速く解けた(282MS).
その他
最初通るわけねーと思ってリアルインプットでテストしながらやってました.ごめんなさい.
間違ったところは,long longを使うとき気をつけなきゃいけない
1LL << (i*N+j))
のLLの部分.わかってはいたのだけど,1LL << 32 == 2^32だけど,1 << 32 == 0.書き忘れていたところが何箇所か・・・
ブログの書き方わかんないから読みにくいかも.ごめんなさい.
ああ、手が痛い.