AOJ 1166 (200)
AOJ-ICPC 2問目
迷路の最短経路を求める。
幅優先探索、距離はans[ ][ ]で管理。
queueにpushするときにans(pushするマスの座標)=ans(今いるマスの座標)+1で更新し、最後はans[h-1][w-1]を出力するようにした。
壁の与えられ方がちょっと複雑だった。
今いるマスの座標を(i, j)とするとき、それぞれの壁が
左:(2*i, j-1)
上:(2*i-1, j)
右:(2*i, j)
下:(2*i+1, j)
となるように壁の情報をdata[ ][ ]に入力した。
あとは、訪れたかどうかを新たに配列を作って管理するとMLEになったので、
ans[i][j]>0のときにはvisitedと判定してqueueに追加しないようにした。
*次のマスをqueueに入れるところの処理が冗長かも