SRM 651 Div1 easy : RobotOnMoon

問題概要:
H * W マスからなるフィールドがあり、各マスは次のいずれかである
'.' : 空マス　移動可能
'#' : 障害物　移動不可能
'S' : ロボットが最初にいる場所　移動可能
ロボットは命令に従って移動する
命令は 'U','D','L','R' で表されるコマンドがいくつか繋がったものとして表される
'U','D','L','R'はそれぞれロボットが1マス上、下、左、右に移動することを意味する
ただし、ロボットが障害物のあるマスへ移動しようとした場合そのコマンドを無視する
ロボットがフィールドの外へ移動した場合、ロボットは消滅する
命令のうち、その命令を実行することでロボットが消滅しないようなものをパーフェクトな命令という
パーフェクトな命令で、その命令のどのような部分列を新たな命令とし実行してもパーフェクトな場合その命令を超パーフェクトな命令という
フィールドの状態が与えられるので、最長の超パーフェクトな命令の長さを答えよ
ただし、無限に命令を長くでくる場合は-1が答えとなる

解法:
ロボットの初期位置から上下左右のいずれかに直進して壁に衝突する場合は答えが-1となる ( その方向のコマンドだけ実行すれば無限に命令を長くできるから )

そうでない場合、上下左右のいずれかの方向だけに移動してロボットが消滅するまでにかかる移動回数から１を引いたものの総和が答えとなる
命令にいずれかのコマンドを入れるとする
この時、そのコマンドを命令に入れることのできる最大の回数というのは
(ロボットがその命令だけを使ってフィールド外にでるまでにかかる移動回数-1)回である
これ以上入れると、命令のうちこのコマンド以外が消えた場合にロボットが消滅してしまう
なのでそれらの総和が答えとなる

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

class RobotOnMoon {
public:
  int h,w;
  inline bool isValid(int x,int y) { return 0 <= x && x < w && 0 <= y && y < h; }
  int longestSafeCommand( vector <string> a ) {
    h = a.size(), w = a[0].size();
    int sx=-1,sy=-1;
    rep(i,h) rep(j,w) if( a[i][j] == 'S' ) {
      sx = j,sy = i;
      break;
    }
    int ret = 0;
    rep(i,4){
      int x = sx, y = sy;
      while( isValid(x+dx[i],y+dy[i]) ){
        x += dx[i], y += dy[i];
        if( a[y][x] == '#' ) return -1;
        ++ret;
      }
    }
    return ret;
  }
};