問題文の解釈がややこしい。
問題
H*Wの2次元グリッドが与えられる。
各セルは空白か埋まっているかのどちらかである。
また、ロボットの初期位置が与えられている。
ここでロボットに'U''D''L''R'の4種類の文字からなるコマンドを与える。
ロボットはそれぞれのコマンドを受けると上・下・左・右の隣接マスに動く。
ただし隣接マスが埋まっている場合は移動しない。
また、グリッドの範囲外に出るとロボットは壊れる。
ここで、ロボットに一連のコマンドを与えたい。
ただしコマンドの一部が消えてしまう可能性がある。
どの部分が消えてもロボットが壊れない最長のコマンド長を答えよ。
解法
初期位置の上下左右方向(遠方でも良い)に埋まったマスがあれば、そちらに向かうコマンドを延々与えてもロボットは壊れないので無限長が解。
それ以外の場合、今の位置を0-indexで(x,y) とすると、左に(x-1)回、右に(W-x-1)回、上に(y-1)回、下に(H-y-1)回まではコマンドを実行しても確実に壊れない。
よって解はそれらの和のH+W-2。
class RobotOnMoon { public: int H,W; int longestSafeCommand(vector <string> B) { H=B.size(); W=B[0].size(); int sy,sx,i,j,x,y; FOR(y,H) FOR(x,W) if(B[y][x]=='S') sy=y,sx=x,B[y][x]='.'; FOR(y,H) if(B[y][sx]=='#') return -1; FOR(x,W) if(B[sy][x]=='#') return -1; return H+W-2; } }
まとめ
解は短いけど、問題文の理解が難しいな。