Free Time Remaining For Today: 4:59
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский
Floodfill©
游戏次数: 427276
胜局数: 209822
In contests, the number of needed colours is not specified.
该页所示题目由Caribou竞赛组委会编写并为其所有
填色游戏指南
正如所介绍的，用最少的颜色来填充一个地图的问题具有很长的历史，比如，在维基百科的文章中.仅用4个颜色就可以填涂一个空白地图的定理是一个有名的只能运用电脑证明而不能被人类计算所证明的头号数学定理。
没有已知算法可以每次都有效率地填涂地图。所谓有效率即指如果有N个很大的区域，那么需要的填色尝试次数只以 Nk增长，k并不取决于N.换句话说，在最有效率的算法中尝试的次数应只以N的多项式增长。然而，已知的填色算法有所谓的指数复杂性，换句话说，填色尝试次数取决于N，比如4N。.
如果可以使用5或6个颜色，或者如果地图只需要两个颜色，最有效率的算法是已知的。
另一个得到最有效率的方法的机会是放弃任何情况下都最有效率这一要求。至少在多数情况下有效的这种探索性步骤（换句话说，一组指令）会在下面进行讨论：
Q.哪个区域应该先被填色？
- 先涂有尽可能多相邻区域的部分会很有效，因为如果该部分被涂上颜色A那么它所有的相邻区域将不能涂颜色A。这会减少这些相邻区域的颜色选择，同时如果填色过难，这将减少后续的尝试次数。
Q.哪一种颜色选择不受限制？
- 在最初填色时使用的颜色一点不受限制。
- 当第二种颜色被第一次使用时，如果这片被涂区域与有第一种颜色的区域相邻，换句话说，如果第二种颜色是有必要的，这种颜色的选择不受限制。
- 当第三种颜色被第一次使用时，如果这片被涂区域与有第一种颜色和有第二种颜色的区域相邻，换句话说，如果第三种颜色是有必要的，这种颜色的选择不受限制。
Q.哪一个区域应该下一个被涂色？
- 下一个要涂的区域应该只有一种可涂颜色，这样我们就不会在涂色上出错。
- 涂色的尝试应小于4N次（对于N个区域的每一个都尝试所有的4种颜色）。所以涂色的尝试次数很大程度上取决于区域的个数N。所以，如果填色后地图的白色（未填涂的）部分被分成了单独而不相邻的，而且后续可被自行填涂的白色子地图，将会很有用。这些区域只有N1和N2个部分(N = N1 + N2)，现在最多只需要4N1 + 4N2次尝试，这比4N1 × 4N2 = 4N次尝试要少得多。
- 如果想要找到填涂一个已知的地图最少的使用的颜色个数，必须先检查2个颜色是否足够。这可以有效率地完成。
如果只有两种颜色A和B可以使用并且其中一个区域已经被涂上一种颜色，那么在交点附近检查可以确定其它所有区域的颜色：
这个规则对于需要用3或4种颜色填涂的首次尝试的地图也适用。例如，如果下方区域1已经有颜色A那么区域2和4需要不同的颜色，我们并不知道有可能是那种颜色但我们知道用颜色A填涂区域3不会影响填涂区域2和4的条件，因为它们已经有相邻的颜色A。
图3只显示了地图的一小部分但是上方的探索性步骤对于任何地图都可以变得更加精准。如果区域3的所有邻近区域（在图3中，区域2和4）都至少有一个相邻的区域被涂上颜色A（在图3中，区域1），那么用颜色A涂区域3不会出错。这是因为这样做不会为其相邻区域带来限制，因为这些区域已经不能使用颜色A。所以如果在后续涂色过程发现了错误（因为颜色的个数不足），区域3也不会有除了A外的其它选择，应该尝试在其它涂色步骤中更改颜色。
- 如果区域3的上方也有一个对角相邻的区域，比如有颜色B的区域9，这会怎么样呢？区域3应该用A或B着色吗？在这里，检查所有3的邻接区域是否已经不可用颜色A或者颜色B将十分有帮助。如果两种情况都不对那么我们可先不涂3.
关注或订阅更新：