読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 11661 : Burger Time?

UVa演習 2014/6/8 (日) 問3

問題リンク:http://uva.onlinejudge.org/external/116/11661.html

問題概要:
長さLの文字列が与えられる
文字列の要素は次の4つのうちのいずれか
'R' : レストラン
'D' : ドラッグストア
'Z' : レストラン & ドラッグストア
'.' : 何もない
レストランとドラッグストアの距離の最小値を求めよ

解法:
左から右へ見ていき、一番最後に見たレストランの場所とドラッグストアの場所を覚えておく
RかDがくる度に場所を更新しつつ距離を計算する
Zがあれば0

コード:

#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;

const int IINF = INT_MAX;
char S[2000010];

void calc(int R,int D,int &ans){
  if( R == -1 || D == -1 ) return;
  ans = min(ans,(int)abs(R-D));
}

int main(){
  int L;
  while( cin >> L, L){
    int R = -1, D = -1, ans = IINF;
    rep(i,L) {
      cin >> S[i];
      if( S[i] == 'R' ) {
        R = i;
        calc(R,D,ans);
      } else if( S[i] == 'D' ) {
        D = i;
        calc(R,D,ans);
      } else if( S[i] == 'Z' ) ans = 0;
    }
    cout << ans << endl;
  }
  return 0;
}