きままにものづくり

日々の気付いたことなんかを書いてます。

SRM651Div1Easy

問題

二次元平面を考える。この平面上にはロボットSと障害物#と空白.がある。
操作者はロボットに対して上下左右の四方向に移動するコマンドを送信できる。移動しようとする先のマスにより、実際の移動が変更される。

  • 移動した先が空白だった場合は、そのマスに移動する
  • 移動した先が障害物だった場合は、移動しない
  • 移動した先が境界の外だった場合は、壊れてしまう

ロボットが壊れないコマンドの最長の長さを求めよ。
長さが固定されない場合は-1を返す。

解法

ロボットの上下左右の直線上に障害物がある場合は-1を返す。
それ以外の場合は、ロボットの上下左右のマージンを全て足し合わせると答えになる。

計算量

 O(WH)
W:平面の幅
H:平面の高さ

コード

広告を非表示にする