题目
n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。
就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。
给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：
dominoes[i] = ‘L’，表示第 i 张多米诺骨牌被推向左侧，
dominoes[i] = ‘R’，表示第 i 张多米诺骨牌被推向右侧，
dominoes[i] = ‘.’，表示没有推动第 i 张多米诺骨牌。
返回表示最终状态的字符串。
示例 1：
输入：dominoes = "RR.L" 输出："RR.L" 解释：第一张多米诺骨牌没有给第二张施加额外的力。
示例 2：
输入：dominoes = ".L.R...LR..L.." 输出："LL.RR.LLRRLL.."
解题
方法一：BFS
由于题目的意思，每1秒，就会有一个会倒，因此可以使用BFS，每一层时间相同，给下一个时刻，施加力，如果该时刻受力平衡（2个力）就忽略，受力不平衡（1个力）就继续传递。
class Solution { public: string pushDominoes(string dominoes) { int n=dominoes.size(); queue<int> q; vector<int> time(n,-1);//记录时间，未访问的为-1 vector<string> force(n);//记录力，(每个点最多只会有2个力) for(int i=0;i<n;i++){ if(dominoes[i]!='.'){ q.push(i); time[i]=0; force[i].push_back(dominoes[i]); } } string res(n,'.'); while(!q.empty()){ int i=q.front(); q.pop(); if(force[i].size()==1){//只有 只到受一个力的 才会继续进行。 如果受到2个力，说明平衡，直接忽略 char f=force[i][0];//当前的 力 res[i]=f; int ni=f=='L'?i-1:i+1;//下一个索引 next index if(ni>=0&&ni<n){ if(time[ni]==-1){//如果下一个点未访问过 q.push(ni); time[ni]=time[i]+1; force[ni].push_back(f); } else if(time[ni]==time[i]+1){//如果下一个点访问过，且时间一致，说明受力平衡 force[ni].push_back(f); } } } } return res; } };
方法二：双指针（模拟）
1、LL之间的全L
2、RR之间的全R
3、LR不变
4、RL中间靠
5、最左边默认有个L，最右边默认有个R，这样方便处理
class Solution { public: string pushDominoes(string dominoes) { dominoes='L'+dominoes+'R'; string res; int l=0,r=1;//通过双指针，处理两指针中间的'.' while(r<dominoes.size()){ while(r<dominoes.size()&&dominoes[r]=='.') r++; char leftChar=dominoes[l]; char rightChar=dominoes[r]; if(leftChar==rightChar){//情况1、2 for(int i=l+1;i<r;i++){ res+=leftChar; } } else if(leftChar=='R'){//情况4：RL中间靠 for(int i=0;i<(r-l-1)>>1;i++) res+='R'; if(((r-l-1)&1)==1) res+='.'; for(int i=0;i<(r-l-1)>>1;i++) res+='L'; } else{//情况3：LR不变 for(int i=l+1;i<r;i++) res+='.'; } res+=rightChar; l=r; r++; } return res.substr(0,res.size()-1); } };
