# 0838. Push Dominoes
###### tags: `Leetcode` `Medium` `BFS`
Link: https://leetcode.com/problems/push-dominoes/
## 思路
BFS 层序遍历
tricky的地方是在我们用forces的值是不是0来判断这里有没有visit过的时候 如何处理有可能一根domino受两边的力然后没有倾斜的情况
解决办法就是遍历每层的时候建另外一个array记录这一层的受力情况 用原本的array检查visited

注意如果用```int[] temp = forces``` temp指向forces的位置 所以temp变forces也会变
用```int[] temp = forces.clone()```就不会有这个问题
## Code

class Solution {
    public String pushDominoes(String dominoes) {
        int[] forces = new int[dominoes.length()];
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<dominoes.length(); i++){
            if(dominoes.charAt(i)!='.'){
                q.add(i);
                forces[i] = dominoes.charAt(i)=='R'?1:-1;
            }
        }
        
        while(!q.isEmpty()){
            int size = q.size();
            int[] temp = forces.clone();
            for(int i=0; i<size; i++){
                int curr = q.poll();
                int next;
                if(forces[curr]==0) continue;
                if(forces[curr]==-1){
                    next = curr-1;
                }
                else{
                    next = curr+1;
                }
                if(next>=0 && next<forces.length && forces[next]==0){
                    temp[next] += temp[curr];
                    q.add(next);
                }
            }
            forces = temp;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<forces.length; i++){
            if(forces[i]==-1) sb.append('L');
            else if(forces[i]==1) sb.append('R');
            else sb.append('.');
        }
        return sb.toString();
    }
}