SRM590 Div1 Easy

250

Rが右に移動している
Lが左に移動している
RとLが交差していない

の３つを確認する

class FoxAndChess {
public:
  string ableToMove(string A, string B)
  {
    const string T = "Possible";
    const string F = "Impossible";

    if (count(A.begin(), A.end(), 'L') != count(B.begin(), B.end(), 'L')) return F;
    if (count(A.begin(), A.end(), 'R') != count(B.begin(), B.end(), 'R')) return F;

    const int size = A.size();

    vector<int> lA;
    vector<int> rA;
    for (int i = 0; i < size; ++i) {
      if (A[i] == 'R') rA.push_back(i);
      if (A[i] == 'L') lA.push_back(i);
    }

    vector<int> lB;
    vector<int> rB;
    for (int i = 0; i < size; ++i) {
      if (B[i] == 'R') rB.push_back(i);
      if (B[i] == 'L') lB.push_back(i);
    }

    const int size_r = rA.size();
    const int size_l = lA.size();

    //
    for (int i = 0; i < size_r; ++i) {
      unless (rA[i] <= rB[i]) return F;
      int cnt_a = 0;
      int cnt_b = 0;
      for (int j = 0; j < size_l; ++j) {
        cnt_a += (lA[j] <= rA[i]);
        cnt_b += (lB[j] <= rB[i]);
      }
      if (cnt_a != cnt_b) return F;
    }

    //
    for (int i = 0; i < size_l; ++i) {
      unless (lA[i] >= lB[i]) return F;
      int cnt_a = 0;
      int cnt_b = 0;
      for (int j = 0; j < size_r; ++j) {
        cnt_a += (rA[j] <= lA[i]);
        cnt_b += (rB[j] <= lB[i]);
      }
      if (cnt_a != cnt_b) return F;
    }

    return T;
  }