曹逸君 Blog · 安卓九宫格的锁屏图案的最长长度

安卓九宫格的锁屏图案的最长长度

题干很简单.求安卓九宫格的锁屏图案的最长长度.

这里重新描述下九宫格锁屏图案规则.

九宫格,3x3的方形点阵
所有点只能经过一次
点与点间连线是直线
不能跨过未经过的点去链接,否则视为先链接中间点再链接对面点.

有些锁屏要求至少链接4个点之类的.与本题无关.忽略.

以有向图建立模型的描述为:

3x3/9个节点.Id从0到8.
起始点入度为0出度为1.截至点入度为1出度为0.
除起始和截至点外,节点入度和出度均为1.[由于本题要链接所有9个节点]
每个节点到其他所有节点的距离都固定且给出.[先忽略规则3.简化起见]

生成邻接矩阵

[   [0.000, 1.000, 2.000, 1.000, 1.414, 2.236, 2.000, 2.236, 2.828],
    [1.000, 0.000, 1.000, 1.414, 1.000, 1.414, 2.236, 2.000, 2.236],
    [2.000, 1.000, 0.000, 2.236, 1.414, 1.000, 2.828, 2.236, 2.000],
    [1.000, 1.414, 2.236, 0.000, 1.000, 2.000, 1.000, 1.414, 2.236],
    [1.414, 1.000, 1.414, 1.000, 0.000, 1.000, 1.414, 1.000, 1.414],
    [2.236, 1.414, 1.000, 2.000, 1.000, 0.000, 2.236, 1.414, 1.000],
    [2.000, 2.236, 2.828, 1.000, 1.414, 2.236, 0.000, 1.000, 2.000],
    [2.236, 2.000, 2.236, 1.414, 1.000, 1.414, 1.000, 0.000, 1.000],
    [2.828, 2.236, 2.000, 2.236, 1.414, 1.000, 2.000, 1.000, 0.000]]

9x9的图看起来吃力.我们看张4x4的.

[   [0.000, 1.000, 1.000, 1.414],
    [1.000, 0.000, 1.414, 1.000],
    [1.000, 1.414, 0.000, 1.000],
    [1.414, 1.000, 1.000, 0.000]]

graph[i][j] 代表的就是节点i到节点j的距离.

所以第一行就是节点0到各个节点的距离.由于我们在求最长距离.故将自己到自己的距离设为0.以免选到自己到自己的路径.

在不考虑规则3的情况下.这是个类似于N皇后的问题.

注意这里贪心算法并不能保证给出最优解.[虽然在4宫格的情况下可以.]

使用回朔算法.

求解大致过程:

给定起始节点0.

将第0列设为0[起始节点不能到达.]

分别考虑第0行所有非0值.[复制当前邻接矩阵] 3.1 选取节点1作为下一个节点. graph[0][1]非零,将graph[0][1]加到长度记录中. 3.2 将第0行以及第1列设为0.因为节点0不能再出发.节点1不能再到达. 3.3 重复此过程直至邻接矩阵全部为0[所有节点都已访问.]

保存当前最优解.

不考虑规则3的解

我闷直接看得到的解吧. 从1出发:

这里直接穿过4从6到达2. 4是最后访问的.

如果没有规则3.我们还可以把所有距离取负值[或者修改松弛过程使得松弛后距离变长]的Dijkstra算法来更快的求解.

由于规则3的存在.使用更通用的回朔算法.

下面增加规则3. 使用一个额外的access_graph来控制是否可以访问.

access_graph = [[1 for _ in range(9)] for _ in range(9)]
breaks =    {   1: [(0, 2)],
                3: [(0, 6)],
                5: [(2, 6)],
                7: [(6, 8)],
                4: [(0, 8), (1, 7), (2, 6), (3, 5)]
                }
for i,j in flaten(breaks.values()):
    access_graph[i][j] = 0
    access_graph[j][i] = 0