はじめに

---

並べられているドミノの初期値が与えられ，これらが最終的にどのような形に落ち着くのかを算出する問題．

各ドミノの状態は，L,R,.の３種類で，それぞれ左に傾いている,右に傾いている,直立しているを表し，直立しているドミノが右から押されたら左に，左から押されたら右に傾く．また，左右から押された場合は直立を維持し，状態は変化しない．

解法

---

まずは傾いているドミノの番号と状態をキューqにプッシュ．

キューに格納されている各ドミノが影響を及ぼすドミノをcommandsにインサート． その時，一つのドミノを左右から押す場合は，commandsから削除する．

以上を繰り返す．

コード全体

---

class Solution {
public:
  string pushDominoes(string dominoes) {
    queue<pair<int, char>> q; // <idx, /[L|R]/>
    map<int, char> commands; // <idx, /[L|R]/>
    for (size_t i=0; i<dominoes.length(); ++i) {
      if (dominoes[i] != '.') {
        q.emplace(i, dominoes[i]);
      }
    }
    while (!q.empty()) {
      while (!q.empty()) {
        size_t idx = q.front().first;
        if (q.front().second == 'L') {
          idx --;
          if (idx == -1) {
            q.pop();
            continue;
          }
        } else {
          /* q.front().second == 'R' */
          idx ++;
          if (idx == dominoes.length()) {
            q.pop();
            continue;
          }
        }

        if (dominoes[idx] == '.') {
          decltype(commands)::iterator found = commands.find(idx);
          if (found == commands.end()) {
            commands.emplace(idx, q.front().second);
          } else {
            commands.erase(found);
          }
        }

        q.pop();
      }

      for (const auto& command: commands) {
        dominoes[command.first] = command.second;
        q.emplace(command);
      }
      commands.clear();
    }
    return dominoes;
  }
};

解説

---

関数

---

戻り値は，ドミノの最終的な状態．

string pushDominoes(string dominoes) {

前準備

---

qは，未処理のドミノを格納するキュー．

commandsは，各ドミノが影響を与えるドミノを格納するハッシュテーブル．

各pair<int,char>は，要素番号および状態(L,R)を意味する．

qには，初期値として，初期状態で傾いているドミノを準備する．

	queue<pair<int, char>> q; // <idx, /[L|R]/>
	map<int, char> commands; // <idx, /[L|R]/>
	for (size_t i=0; i<dominoes.length(); ++i) {
		if (dominoes[i] != '.') {
			q.emplace(i, dominoes[i]);
		}
	}

ループ

---

すべてのドミノが処理済みとなるまでループする．

	while (!q.empty()) {

q でループ

---

qの先頭から順に，左端のLおよび右端のRは無視しながらループ．

		while (!q.empty()) {
			size_t idx = q.front().first;
			if (q.front().second == 'L') {
				idx --;
				if (idx == -1) {
					q.pop();
					continue;
				}
			} else {
				/* q.front().second == 'R' */
				idx ++;
				if (idx == dominoes.length()) {
					q.pop();
					continue;
				}
			}

ドミノの与える影響を算出

---

Lの場合は左に，Rの場合は右に影響を及ぼすため，その情報をcommandsに保存．

この時，左右から押される場合はcommandsから削除する．

			if (dominoes[idx] == '.') {
				decltype(commands)::iterator found = commands.find(idx);
				if (found == commands.end()) {
					commands.emplace(idx, q.front().second);
				} else {
					commands.erase(found);
				}
			}

ドミノを処理済みにする

---

qをポップして次のドミノを先頭にする．

			q.pop();
		}

ドミノの状態を更新

---

commandsを使って，ドミノの状態を書き換える．

		for (const auto& command: commands) {
			dominoes[command.first] = command.second;
			q.emplace(command);
		}
		commands.clear();
	}

処理の終了

---

	return dominoes;
}

おわりに

---

なんか他の人のソリューションのほうがパフォーマンスが良いので悲しい．

参考

---

• https://leetcode.com/problems/push-dominoes