2019-05-05 AOJ 1140 Cleaning Robot (ICPC Domestic 2005 F) AOJ ICPC DP 最短経路 judge.u-aizu.ac.jp 街(この問題ではスタート地点および汚れた床)の間の距離を求めるのにBFSしないといけないので面倒だが、それさえやってしまえばTSPを書くだけの問題。TSPについては停止条件でスタート地点に戻る必要がない点について注意が必要。 実装力が皆無なので、最初のコードを書いた時点で50分くらいかかってしまった。その上、スタート地点を勝手に最も左上にあると仮定したコードになっていた、BFSの停止条件のミス、到達不可能な場合の判定の出力でミスをしてしまい、これら全てテストケースでは気づけなかったので何度もWAを出してしまった。細かいミスを無くしていきたい。 judge.u-aizu.ac.jp