用回溯法计算消消乐游戏最大得分
前言
这是一个非常非常简单的消消乐游戏。在一个 M*N 的网格中，一共有种物品。玩家可以列向或者行向得交换两个物品。当列向或者行向存在3 ～ 5个连续的相同物品时就可以消除将这些物品。消除3,4,5个连续的相同物品的得分分别为1,3,10。当物品被消除之后，上方的物品会垂直下落对空缺进行填补。如果填补之后依旧存在3～5个连续且相同的物品，则继续进行消除。如果交换操作无法消除任何物品，则禁止该操作。题目要求在指定的步数内拿到最高的分数。
如上图所示，交换了图中2和3之后，会存在连续的4个2和3个3的情况，然后会一起消除，得分为 1 + 3 = 4分。事实上，再消除完成之后，上方的物品掉落下来会出现连续的3个2和4个4还可以消除。
写个简单的消消乐
基本算法思路及需要解决的问题
基本的算法思路如下：
- 交换两个需要交换的点；
- 从交换的点出发，分别统计上下左右与之连续且相同的元素的数量，并按照记分规则进行记分。如果交换之后无法消除任何元素，则禁止点的交换。
- 消除需要消除的元素，然后将消除的元素上方的元素进行下移操作以填补空缺，顶部落空的位置则标记为无物品；
- 进行全盘的检查，对每个点按照步骤2中的方法进行标记记分；
- 如果全盘检查发现还存在可以消除的元素，则回到步骤3进行执行，否则结束检查调整。
为了实现用回溯法解决计算消消乐游戏最大得分问题，我们需要先实现一个简单的消消乐游戏。消消乐游戏需要解决的两个主要的问题如下（这里称游戏的网格为棋盘）：
- 检查是否存在连续 3～5个连续且相同物品
- 计算消除物品之后的得分
- 消除物品和物品下落之后棋盘调整
问题1: 检查是否存在连续 3～5个连续且相同物品
根据游戏规则，每次操作都是在交换了两个相邻的点，那么我们只要从交换的点开始进行对上下左右的四个方向进行检查。为了方便程序的实现，我们实现了如下四个方向的Enum类，其中的Point类只有row和col两个属性。
ArrowE.class
public enum ArrowE {
UP(1, "^", "up", new Point(-1, 0)),
RIGHT(2, ">", "right", new Point(0, 1)),
DOWN(3, "v", "down", new Point(1, 0)),
LEFT(4, "<", "left", new Point(0, -1))
;
private final int value;
private final String arrow;
private final String name;
private final Point vector;
private static final Map<ArrowE, ArrowE> arrowMapReverse;
static {
arrowMapReverse = new HashMap<ArrowE, ArrowE>();
addReverse(ArrowE.UP, ArrowE.DOWN);
addReverse(ArrowE.LEFT, ArrowE.RIGHT);
}
// getters and setters
...
// 获取相反方向的方法
public ArrowE getReverse() {
return arrowMapReverse.get(this);
}
}基本的思路很简单，从一个点出发，分别计算向上和下与之相同的物品的总数numUp和numDown，以及分别向左和向右与相同的物品的总数numLeft和numRight。然后按照计算规则计算 numUp + 1 + numDown 和 numLeft + 1 + numRight 的得分即可，如果得分大于 0，则执行物品消除的操作，否则不计算进行后续操作。
按照上面的逻辑，似乎很简单，而且马上就可以进行消除了，似乎只要消除交换点和numUp numDown numLeft numRight规定的范围就可以了。然而在实际的操作中，会出现更加复杂的场景。如下图：
在正常的交换之后，可以通过上面描述的方式对交换点的行列进行检查，并标记可消除的位置。但是交换之后，由于物品的掉落，会出现非常复杂的场景，如上图中的图三。甚至还可以出现更加复杂的情况，就是出现多个可以消除的不相连的区域。对于这种情况，只能对整个棋盘进行检查判断，找到所有可以消除的区域。
上图中的图三的可消除区域存在2个行和4个列，其中的一些位置会同时作用于一个行和列当中，如[3, 0], [3, 1]等。通过设计一个标记值，标记一个元素参与了行或者是列的消除。标记值为1时，表示该元素会在行中消除，2是为列中消除，3表示同时在行和列中消除（这里的1 + 2 = 3非常的巧妙）。如果一个点参与了行的消除，那么这个点就不能再参与其他行的消除，但可以继续参与其他列的消除。同理，如果这个点参与了列的消除，则这个点就不能再参与其他列的消除，但可以参与其他列的消除。当标记位置的值为3时，则该点无法继续参与其他行或者列的消除。
由于需要消除的元素构成的区域，无法简单的从一个点向上下左右进行拓展，因此需要设计一个二维数组进行标记。上图图3可以得到如下的标记位图。
在进行标记的过程中，可以按照简单版的方式进行记分，也可以直接对标记的二维数组进行行列统计记分。
问题2: 计算消除物品之后的得分
上面已经简单的说明了，这里就不再重复说明。
问题3: 消除物品和物品下落之后棋盘调整
消除操作对于整个过程来说也比较重要，但说简单也不简单，说复杂也不复杂。根据二维标记数组，找到存在需要消除的元素的列，进行列上的下落操作。核心的代码也就只有如下的一行：
chessboard[row][col] = chessboard[row - offset][col];列消除下落的完整代码如下：
/**
* 将第 col 列的，位于(row, col)上方offset距离的点下落位置到从(row, col)开始向上的位置
* 这将会从(row, col)开始覆蓋
* <pre>
* 0 0 0 0 0
* 0 0 0 1 0
* 0 0 0 x 0
* 0 0 0 x 0
* 0 0 0 * 0
* 0 0 0 (*) 0
* v
* row = row(*),col=col(*),offset=num(*)
* v
* 0 0 0 0 0
* 0 0 0 0 0
* 0 0 0 0 0
* 0 0 0 1 0
* 0 0 0 x 0
* 0 0 0 x 0
* </pre>
* @param row 目的位置的行号
* @param col 目的位置的列号
* @param offset 下降距离
*/
private void dropColDownTo(int row, int col, int offset) {
if(offset == 0) {
return;
}
while(row - offset >= 0) {
// 如果 chessboard[row][col] == 0，则表示 chessboard[row][col] 上方的所有点都是 0
chessboard[row][col] = chessboard[row - offset][col];
row --;
}
while(row >= 0 && chessboard[row][col] != 0) {
chessboard[row][col] = 0;
row --;
}
}完整的对整个棋盘进行调整的实现为如下的一个双重for循环。这里有一个细节需要特别注意，也就是必须对每一列从上到下进行调整。因为如果从下到上进行调整，会改变上方的元素原本的位置。从而导致调整之后调整上方元素的时候没有调整到正确的元素。
/**
* 在指定的范围内，消除标记了的元素。消除方法为：从左到右对每一列进行检测，然后对每一列从上到下进行消除和下落。
* <pre>
* 0 0 0 0
* (1)(1)(1) 0
* 3 3 2 0
* 4 (2)(2)(2)
*
* 0 0 0 0
* (0)(1)(1) 0
* 3 3 2 0
* 4 (2)(2)(2)
*
* 0 0 0 0
* (0)(0)(1) 0
* 3 3 2 0
* 4 (2)(2)(2)
*
* 0 0 0 0
* (0)(0)(1) 0
* 3 3 2 0
* 4 (0)(2)(2)
* </pre>
* @param range 需要调整的范围
* @param marks 标记需要消除的元素
*/
private void eliminateAndDropDownAdjust(DetectionRange range, int[][] marks) {
for(int c = range.getColLeft(); c <= range.getColRight(); c ++) {
// 对每一列进行调整，从上到下
for(int r = range.getRowTop(); r <= range.getRowBottom(); r ++) {
// 计算被消除的列长度
int originalR = r;
while(r <= range.getRowBottom() && marks[r][c] != 0) {
// 取消标记
marks[r ++][c] = 0;
}
dropColDownTo(r - 1, c, r - originalR);
}
}
}这里其实基本上已经完成了物品的消除和棋盘的调整。但可以注意到，上面的代码中有一个特别的类 DetectionRange。该类如同它的名字一样，为“检测范围”，在统计为需要元素和计算得分之后，并不需要对整个棋盘进行调整，仅需要对受影响的范围进行调整即可。通过对范围的限制，可以减少部分计算。
还有一点小小的优化在上方提及的，就是进行检测的时候全盘检测的时候是从左下角开始，分别向右和上进行检查。这是因为在进行消除之后，顶部的都是没有物品的位置，对其再进行重复的检测没有意义。此外，仅仅检测“右”和“上”两个方向即可覆蓋全部检测，无需再进行”左“和”下“的检测，因为“右”和“左”，“上”和“下”是可以等价的。
用回溯法计算消消乐游戏最大得分
整体实现而言，都是很传统的回溯法实现方式。基本的思路如下：
MasScore(xiaoXiaoLeGame, leftStep) = MaxScore(everyPointInChess, xiaoXiaoLeGame, leftStep);
MaxScore(pointInChess, xiaoXiaoLeGame, leftStep) =
max(向右交换得分 + MaxScore(xiaoXiaoLeGame.exchange(pointInChess, Right), leftStep - 1)，
向上交换得分 + MaxScore(xiaoXiaoLeGame.exchange(pointInChess, Up), leftStep - 1))；因为消消乐游戏的代码实现得比较完善，因而实现的代码也没有太多，这里就全部粘贴出来了。
package cn.donespeak.xiaoxiaole;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import cn.donespeak.xiaoxiaole.XiaoXiaoLe.OperationForbiddenException;
public class AutoPlayer {
private XiaoXiaoLe xiaoXiaoLe;
private int stepsLeft;
private List<TipsPoint> tips;
private int maxScore;
public AutoPlayer(XiaoXiaoLe xiaoXiaoLe, int stepsLeft) {
this.xiaoXiaoLe = xiaoXiaoLe;
this.stepsLeft = stepsLeft;
this.tips = new LinkedList<TipsPoint>();
this.maxScore = 0;
}
public void start() {
maxScore = getMaxScore(xiaoXiaoLe, stepsLeft, tips);
}
public int getMaxScore() {
return maxScore;
}
public List<TipsPoint> getTips() {
return tips;
}
private int getMaxScore(XiaoXiaoLe xiaoXiaoLe, int stepsLeft, List<TipsPoint> tips) {
if(stepsLeft == 0) {
return 0;
}
int maxScore = 0;
List<TipsPoint> tipsPicked = new ArrayList<>();
for(int r = xiaoXiaoLe.getRowNum() - 1; r >= 0; r --) {
for(int c = 0; c < xiaoXiaoLe.getColNum(); c ++) {
if(xiaoXiaoLe.getChessboardCell(r, c) == 0) {
continue;
}
List<TipsPoint> tipsRight = new ArrayList<>();
List<TipsPoint> tipsUp = new ArrayList<>();
XiaoXiaoLe xiaoXiaoLeRight = xiaoXiaoLe.getSnapshot();
XiaoXiaoLe xiaoXiaoLeUp = xiaoXiaoLe.getSnapshot();
int scoreRight = exchangeRight(xiaoXiaoLeRight, r, c, stepsLeft, tipsRight);
int scoreUp = exchangeUp(xiaoXiaoLeUp, r, c, stepsLeft, tipsUp);
int maxIncreasement = Math.max(scoreRight, scoreUp);
maxScore = Math.max(maxIncreasement, maxScore);
if(maxIncreasement == maxScore) {
if(maxIncreasement == scoreRight) {
if(scoreRight == scoreUp) {
// 两个方法得分相同时候，取路径最短的
tipsPicked = tipsRight.size() < tipsUp.size()? tipsRight: tipsUp;
} else {
tipsPicked = tipsRight;
}
} else if(maxIncreasement == scoreUp) {
tipsPicked = tipsUp;
}
}
}
}
tips.addAll(tipsPicked);
return maxScore;
}
private int exchangeUp(XiaoXiaoLe xiaoXiaoLe, int r, int c, int stepsLeft, List<TipsPoint> tips) {
return exchange(xiaoXiaoLe, r, c, stepsLeft, ArrowE.UP, tips);
}
private int exchangeRight(XiaoXiaoLe xiaoXiaoLe, int r, int c, int stepsLeft, List<TipsPoint> tips) {
return exchange(xiaoXiaoLe, r, c, stepsLeft, ArrowE.RIGHT, tips);
}
private int exchange(XiaoXiaoLe xiaoXiaoLe, int r, int c, int stepsLeft, ArrowE arrow,
List<TipsPoint> tips) {
int increasement = 0;
try {
tips.add(new TipsPoint(r, c, arrow));
increasement += xiaoXiaoLe.exchangeWith(r, c, arrow);
increasement += getMaxScore(xiaoXiaoLe, stepsLeft - 1, tips);
// 如果操作允许，也就是没有抛出异常，其该操作得到分数，则添加该操作
} catch (OperationForbiddenException e) {
// do nothing
} finally {
if(increasement == 0) {
tips.remove(tips.size() - 1);
}
}
return increasement;
}
}上面代码的TipPoint的基本结构如下：
public class TipsPoint extends Point {
// 可以考虑加入方向 ArrowE
private ArrowE arrow;
}整体而言，实现的难度在于消消乐游戏的实现，而不在于回溯法的是实现。
完整的代码实现见：relaxinginjava/xiaoxiaole @Github
相关文章