.png){kind=icon}
返回
A linear-time algorithm for the two-color one-dimensional buttons & scissors
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ipl.2026.106622.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
确定给定的“按钮与剪刀”拼图棋盘是否有解的问题已知为NP完全问题。另一方面，当棋盘限制为一维时，已知对于大小（长度）为n的棋盘可在O(n³)时间内求解。这一结论在按钮颜色限制为两种颜色时也成立。我们提供了一个简单的线性时间算法，用于判定“双色一维按钮与剪刀”问题的输入是否有解。该算法在应用线性时间预处理后使用一个必要且充分的条件。
Keyword:
Buttons & scissors
Puzzle
Linear-time algorithm
Necessary and sufficient condition
Run-length encoding
期刊
I
IF:
0.6
论文数:
17
被引数:
3.4K
.png){kind=icon}
