屏幕方案数再修正readme.pdfVIP

问题描述

屏幕锁定后，会出现3×3共9个点。手指按在屏幕上，不能离开，当手指经过一

个点的时候，该点会被标记，连续经过若干个点划出若干段线段就能构成一个图案。

经我尝试，上的图案满足以下几个条件：

图案的线段可以出现交叉。

图案相同但是笔划顺序不同，或者是旋转、对称后可以重合的图案，它们都属于不同

的图案。

系统出于安全的考虑，图案至少需要使4个点被标记。

任意一个点在图案中只会被标记一次，如果图案的交叉位置在一个点上，这个点

也只会在第一次被标记。

3×3的点中存在三点共线的情况，在同一直线上，不可能绕过中间的点连接上处于其

两端的两点。如果中间的点未被标记，尝试连接两端两点会使中间的点被标记；如果中间

的点已经被标记，那么两端的两点可以直接连接。

问题分析

如果没有上述条件限制，那么图案总数是一个

非常简单的组合问题：第一个点可以选择9个位置，第

二个点8个位置，……可得一共有∑∏

986409种方案。

为了分析简单，我们以坐标来描述这九个点（见右

图）。

条件4的限制可以描述为，在直线中间的点还没有标记的时候，下述8个点对不能直

接连接：

(0,0)和(2,2)

(0,2)和(2,0)

(0,0)和(0,2)

(0,0)和(2,0)

(2,2)和(0,2)

(2,2)和(2,0)

(1,0)和(1,2)

(0,1)和(2,1)

考虑上上述条件，计数变得非常复杂。

算法描述

本程序采用广度优先有哪些信誉好的足球投注网站算法，从一个起点开始，在当前状态下，找出所有可以作为

下一个点，产生出新的图案，然后将其加入队列。遍历整个队列，对队列中的每一个

图案都进行上述的操作，直到队列里没有新的点为止。

由于图案最多不超过9个点，方案总数小于上述没有任何限制的986409种，因此

该算法是可行的。

程序运行

双击运行屏幕方案数.exe,即可生成并输出n位的数目（0n10）。