n 张多米诺骨牌排成一行 将每张多米诺骨牌垂直竖立. 在开始时 同时把一些多米诺骨牌向左或向右推.
每过一秒 倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌. 同样地 倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌.
如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时 由于受力平衡 该骨牌仍然保持不变.
就这个问题而言 我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力.
给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态 其中:
解释: 第一张多米诺骨牌没有给第二张施加额外的力.
当时间为 $0$ 时 部分骨牌会受到一个初始的向左或向右的力而翻倒. 过了 $1$ 秒后 这些翻倒的骨牌会对其周围的骨牌施加一个力. 具体表现为:
向左翻倒的骨牌 如果它有直立的左边紧邻的骨牌 则会对该直立的骨牌施加一个向左的力.
向右翻倒的骨牌 如果它有直立的右边紧邻的骨牌 则会对该直立的骨牌施加一个向右的力.
接下去需要分析这些 $1$ 秒时受力的骨牌的状态. 如果仅受到单侧的力 它们会倒向单侧; 如果受到两个力 则会保持平衡. 再过 $1$ 秒后 这些新翻倒的骨牌又会对其他直立的骨牌施加力 而不会对正在翻倒或已经翻倒的骨牌施加力.
这样的思路类似于广度优先搜索. 我们用一个队列 $q$ 模拟搜索的顺序; 数组 $\textit{time}$ 记录骨牌翻倒或者确定不翻倒的时间 翻倒的骨牌不会对正在翻倒或者已经翻倒的骨牌施加力; 数组 $\textit{force}$ 记录骨牌受到的力 骨牌仅在受到单侧的力时会翻倒.
我们可以枚举所有连续的没有被推动的骨牌，根据这段骨牌的两边骨牌（如果有的话）的推倒方向决定这段骨牌的最终状态：
如果两边的骨牌同向，那么这段连续的竖立骨牌会倒向同一方向。
如果两边的骨牌相对，那么这段骨牌会向中间倒。
如果两边的骨牌相反，那么这段骨牌会保持竖立。
特别地，如果左侧没有被推倒的骨牌，则假设存在一块向左倒的骨牌；如果右侧没有被推倒的骨牌，则假设存在一块向右倒的骨牌。这样的假设不会破坏骨牌的最终状态，并且边界情况也可以落入到上述三种情况中。
）未匹配，向左侧倒下，至0或者已倒下位置；
（未匹配，向右侧倒下，至尾或者已倒下位置；