E. Robot on the Board 1

問題

• https://codeforces.com/contest/1607/problem/E
• 問題概要
  • ロボットがステージ上を命令どおりに動く。ステージから落ちたら死ぬ。できるだけ生き残るにはどの座標から始めればいいか？
• AC
  • ✅https://codeforces.com/contest/1607/submission/134177705

解説

• ステージ上のどの領域が「生きている領域」かを管理する
• 例えば3x3のステージで最初の移動が右だった場合、右端の領域は死ぬ（画像参照）
• これはAtCoderで類題があったはず（思い出したら追記する）

void solve(){
  ll H,W;cin>>H>>W;
  string s;cin>>s;

  // 安全地帯 y方向
  ll upper=1;
  ll lower=H;

  // 安全地帯 x方向
  ll left=1;
  ll right=W;

  // ロボットの位置のmin, max
  ll y_min=0;
  ll y_max=0;
  ll x_min=0;
  ll x_max=0;

  // ロボットの位置
  ll y=0;
  ll x=0;

  for(char c : s){
    if(c=='L'){
      x--;
      if(x<x_min){
        left++;
      }
    }
    else if(c=='R'){
      x++;
      if(x>x_max){
        right--;
      }
    }
    else if(c=='D'){
      y++;
      if(y>y_max){
        lower--;
      }
    }
    else if(c=='U'){
      y--;
      if(y<y_min){
        upper++;
      }
    }

    if(left>right){
      if(c=='R'){
        p2(upper,left);return;
      }else{
        p2(upper,right);return;
      }
    }

    if(upper>lower){
      if(c=='U'){
        p2(lower,left);return;
      }else{
        p2(upper,left);return;
      }
    }

    chmin(y_min,y);
    chmax(y_max,y);

    chmin(x_min,x);
    chmax(x_max,x);
  }

  // 最後まで生き延びた場合
  p2(upper,left);return;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;

    while(N--)solve();
    
    return 0;
}