幅優先探索 + ビットDP 汚れたマスを都市とした巡回セールスマン問題と見なせる。（ただしスタート地点に戻る必要はない) 事前に汚れたマス同士の距離を幅優先探索で計算し、あとはビットDPで計算。 int w,h; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1};…