arrays - 'Pogo Painter' 小游戏的算法

Question

我正在开发一款名为“Pogo Painter”的迷你游戏，我需要一些数学解决方案。下面是一张图片(用 Paint 制作)来说明它的全部内容。

四名不同颜色的玩家必须占据方 block 才能获得分数。迷你游戏类似于:http://www.youtube.com/watch?v=rKCQfAlaRrc ，但略有不同。玩家将被允许在 Playground 上跑来跑去并占据任何一个方 block ，并在模式关闭时收集积分。例如，在 A3 上认领蓝色方 block 将创建一个封闭的蓝色图案。

我应该声明什么样的变量以及如何检查形态是否闭合？

如果你有解决办法请回答:)

Answer 1

这是为您的问题建模的另一种(离散优化)方法。

符号

将您的网格视为具有 n^2 个节点和长度为 1 的边(边连接两个相邻节点)的“图形”。让节点编号为 1:n^2。 (为了便于表示，您可以根据需要使用双数组 (x,y) 来表示每个节点。)

决策变量

有 k 种颜色，每个玩家一种(1 到 4)。 0 是无人认领的单元格(白色)

X_ik = 1 if player k has claimed node i.  0 otherwise.

开始

X_i0 = 1 for all nodes i. 

所有节点开始时都是白色 (0)。

相邻集:如果两个节点 i 和 j 彼此相邻，则它们是“邻居”。 (任何给定的节点 i 最多可以有 4 个邻居:上下左右。)

边缘变量:我们现在可以定义一组新的边变量 Y_ijk，它们连接两个具有共同颜色 k 的相邻节点(i 和 j)。

Y_ijk = 1 if neighboring nodes i and j are both of color k. 0 Otherwise.
(That is, X_ik = X_jk) for non-zero k.

我们现在有一个无向图。检查“闭合模式”与检测周期相同。

检测周期:

A simple DFS搜索就可以了，因为我们有无向循环。从每个彩色节点 i 开始，并检查循环。如果路径将您带回访问过的节点，则存在循环。您可以相应地奖励积分。

最后，在您设计游戏时提出一个建议。您可以根据检测到的“最长周期”进行奖励积分。最短的循环获得 4 分，每条边获得一分(或循环中的每个节点获得一分)，以最适合您的方式为准。

1 1
1 1    scores 4 points

1 1 1
1 1 1 scores 6 points

1 1 1
1 1 1
1 1    scores 8 points 

希望对您有所帮助。