每日算法 — 使用java实现消消乐：BFS连通检测与贪心消除链式反应

引言

消消乐（Match-3）是全球最受欢迎的三消益智游戏之一。玩家在棋盘上交换相邻元素，使三个或以上同色元素连成一线即可消除，消除后上方元素下落填补空位，可能引发连锁反应。本文将用Java实现消消乐的核心消除逻辑，重点讲解BFS连通块检测算法、贪心策略选择最优消除顺序，以及链式反应模拟机制。

问题建模

消消乐的核心数据结构是一个二维棋盘，每个格子存储一种颜色或元素类型。关键算法问题包括：

1. 连通检测：如何快速找到所有可消除的元素组（横向或纵向连续三个以上同色）
2. 消除与下落：消除后如何让上方元素下落填补空位
3. 链式反应：下落后的新棋盘是否又形成了新的可消除组
4. 贪心决策：当存在多个可消除组时，如何选择最优的消除顺序以获得最高分数

核心算法设计

1. BFS连通块检测

对于棋盘上的每一个未访问的格子，我们可以使用BFS或DFS来找到所有与其相连的同色元素。但更高效的方式是分别扫描行和列：

• 横向扫描：逐行检查，找到横向连续三个以上同色的元素组
• 纵向扫描：逐列检查，找到纵向连续三个以上同色的元素组
• 合并标记：将所有找到的可消除格子标记出来

2. 消除与重力下落

标记完成后，我们需要：

1. 将所有标记的格子置为空（特殊值，如0）
2. 对每一列，将所有非空元素向下压缩（类似于冒泡排序的逆向操作）
3. 在顶部补充新元素

3. 贪心消除策略

当棋盘上同时存在多个可消除组时，贪心策略的目标是最大化总分。常见的贪心启发式包括：

• 优先消除大的连通块（4个以上通常有特殊奖励）
• 优先消除底部元素（可能引发更大的连锁反应）
• 优先消除能制造特殊道具的组合

Java完整实现

import java.util.*;

/**
 * 消消乐核心算法实现
 * 包含BFS连通检测、消除下落、链式反应与贪心策略
 */
public class Match3Game {

    // 棋盘大小
    private static final int ROWS = 8;
    private static final int COLS = 8;
    // 元素类型数量（颜色种类）
    private static final int TYPES = 5;
    // 空格子标记
    private static final int EMPTY = 0;

    private int[][] board;
    private Random random;
    private int score;

    public Match3Game() {
        this.board = new int[ROWS][COLS];
        this.random = new Random();
        this.score = 0;
        initializeBoard();
    }

    /**
     * 初始化棋盘，确保没有初始可消除组合
     */
    private void initializeBoard() {
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                int type;
                do {
                    type = random.nextInt(TYPES) + 1;
                } while (wouldFormMatch(i, j, type));
                board[i][j] = type;
            }
        }
    }

    /**
     * 检查在(i,j)放置type是否会形成三连
     */
    private boolean wouldFormMatch(int row, int col, int type) {
        // 检查横向
        int count = 1;
        // 向左检查
        for (int c = col - 1; c >= 0 && board[row][c] == type; c--) count++;
        // 向右检查
        for (int c = col + 1; c < COLS && board[row][c] == type; c++) count++;
        if (count >= 3) return true;

        // 检查纵向
        count = 1;
        // 向上检查
        for (int r = row - 1; r >= 0 && board[r][col] == type; r--) count++;
        // 向下检查
        for (int r = row + 1; r < ROWS && board[r][col] == type; r++) count++;
        return count >= 3;
    }

    /**
     * BFS连通检测：找到所有可消除的元素组
     * 返回标记数组，true表示该位置需要消除
     */
    public boolean[][] findMatches() {
        boolean[][] toRemove = new boolean[ROWS][COLS];

        // 横向扫描
        for (int i = 0; i < ROWS; i++) {
            int count = 1;
            for (int j = 1; j <= COLS; j++) {
                if (j < COLS && board[i][j] != EMPTY && board[i][j] == board[i][j-1]) {
                    count++;
                } else {
                    if (count >= 3) {
                        for (int k = j - count; k < j; k++) {
                            toRemove[i][k] = true;
                        }
                    }
                    count = 1;
                }
            }
        }

        // 纵向扫描
        for (int j = 0; j < COLS; j++) {
            int count = 1;
            for (int i = 1; i <= ROWS; i++) {
                if (i < ROWS && board[i][j] != EMPTY && board[i][j] == board[i-1][j]) {
                    count++;
                } else {
                    if (count >= 3) {
                        for (int k = i - count; k < i; k++) {
                            toRemove[k][j] = true;
                        }
                    }
                    count = 1;
                }
            }
        }

        return toRemove;
    }

    /**
     * 计算本次消除的基础分数
     * 消除n个元素得 n * n * 10 分
     */
    private int calculateScore(boolean[][] toRemove) {
        int count = 0;
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (toRemove[i][j]) count++;
            }
        }
        return count * count * 10;
    }

    /**
     * 执行消除并重置被标记的格子
     */
    private int removeMatches(boolean[][] toRemove) {
        int removed = 0;
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (toRemove[i][j]) {
                    board[i][j] = EMPTY;
                    removed++;
                }
            }
        }
        return removed;
    }

    /**
     * 重力下落：每列的非空元素下沉到底部
     */
    public void applyGravity() {
        for (int j = 0; j < COLS; j++) {
            int writePos = ROWS - 1;
            for (int i = ROWS - 1; i >= 0; i--) {
                if (board[i][j] != EMPTY) {
                    board[writePos][j] = board[i][j];
                    if (writePos != i) {
                        board[i][j] = EMPTY;
                    }
                    writePos--;
                }
            }
            // 在顶部填充新元素
            for (int i = writePos; i >= 0; i--) {
                board[i][j] = random.nextInt(TYPES) + 1;
            }
        }
    }

    /**
     * 链式反应：重复消除直到没有可消除的组合
     * 返回总消除次数和总分数
     */
    public ChainResult processChainReaction() {
        int totalScore = 0;
        int chainCount = 0;
        int multiplier = 1;

        while (true) {
            boolean[][] matches = findMatches();
            if (!hasAnyMatch(matches)) break;

            int baseScore = calculateScore(matches);
            totalScore += baseScore * multiplier;
            removeMatches(matches);
            applyGravity();

            chainCount++;
            multiplier++; // 连锁反应分数倍率递增
        }

        return new ChainResult(chainCount, totalScore);
    }

    /**
     * 检查是否有任何可消除的元素
     */
    private boolean hasAnyMatch(boolean[][] matches) {
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                if (matches[i][j]) return true;
            }
        }
        return false;
    }

    /**
     * 贪心策略：评估当前棋盘所有可能的交换，选择得分最高的操作
     * 返回最佳交换位置和预期得分
     */
    public Move findBestMove() {
        Move bestMove = null;
        int bestScore = -1;

        // 遍历所有相邻交换
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                // 尝试与右侧交换
                if (j + 1 < COLS) {
                    int score = evaluateSwap(i, j, i, j + 1);
                    if (score > bestScore) {
                        bestScore = score;
                        bestMove = new Move(i, j, i, j + 1);
                    }
                }
                // 尝试与下方交换
                if (i + 1 < ROWS) {
                    int score = evaluateSwap(i, j, i + 1, j);
                    if (score > bestScore) {
                        bestScore = score;
                        bestMove = new Move(i, j, i + 1, j);
                    }
                }
            }
        }

        return bestMove;
    }

    /**
     * 评估一次交换的预期得分（模拟交换并计算链式反应分数）
     */
    private int evaluateSwap(int r1, int c1, int r2, int c2) {
        // 保存原棋盘状态
        int[][] original = copyBoard();

        // 执行交换
        int temp = board[r1][c1];
        board[r1][c1] = board[r2][c2];
        board[r2][c2] = temp;

        // 检查交换后是否形成消除
        boolean[][] matches = findMatches();
        if (!hasAnyMatch(matches)) {
            // 无消除，恢复棋盘
            board = original;
            return -1; // 无效操作
        }

        // 模拟链式反应
        ChainResult result = processChainReaction();
        int score = result.totalScore;

        // 恢复棋盘
        board = original;
        return score;
    }

    /**
     * 深拷贝棋盘
     */
    private int[][] copyBoard() {
        int[][] copy = new int[ROWS][COLS];
        for (int i = 0; i < ROWS; i++) {
            System.arraycopy(board[i], 0, copy[i], 0, COLS);
        }
        return copy;
    }

    /**
     * 执行玩家的一次交换操作
     */
    public ChainResult makeMove(int r1, int c1, int r2, int c2) {
        // 交换
        int temp = board[r1][c1];
        board[r1][c1] = board[r2][c2];
        board[r2][c2] = temp;

        // 处理链式反应
        return processChainReaction();
    }

    public void printBoard() {
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                System.out.printf("%d ", board[i][j]);
            }
            System.out.println();
        }
        System.out.println("Score: " + score);
    }

    // 辅助类
    static class ChainResult {
        int chainCount;
        int totalScore;
        ChainResult(int chainCount, int totalScore) {
            this.chainCount = chainCount;
            this.totalScore = totalScore;
        }
    }

    static class Move {
        int r1, c1, r2, c2;
        Move(int r1, int c1, int r2, int c2) {
            this.r1 = r1; this.c1 = c1;
            this.r2 = r2; this.c2 = c2;
        }
        @Override
        public String toString() {
            return String.format("(%d,%d) <-> (%d,%d)", r1, c1, r2, c2);
        }
    }

    public static void main(String[] args) {
        Match3Game game = new Match3Game();
        System.out.println("初始棋盘:");
        game.printBoard();

        // AI寻找最佳移动
        Move best = game.findBestMove();
        System.out.println("\nAI推荐最佳移动: " + best);

        if (best != null) {
            ChainResult result = game.makeMove(best.r1, best.c1, best.r2, best.c2);
            System.out.println("执行后触发 " + result.chainCount + " 次连锁反应");
            System.out.println("获得总分: " + result.totalScore);
            System.out.println("\n新棋盘:");
            game.printBoard();
        }
    }
}

复杂度分析

对于8×8的棋盘，贪心策略每次需要评估约112次交换，每次评估需要模拟链式反应，整体在可接受范围内。对于更大棋盘，可考虑启发式剪枝减少搜索空间。

算法优化方向

1. 增量检测：不必每次重新扫描整个棋盘，只需检测受交换或下落影响的区域
2. 特殊元素：实现炸弹（消除周围）、火箭（消除整行/列）等特殊元素的连锁触发逻辑
3. Minimax对手：在PVP模式中，可使用Minimax算法预测对手最优操作并制定防御策略
4. 位运算加速：使用位掩码表示棋盘状态，加速连通检测和状态评估

总结

消消乐的核心算法并不复杂，BFS/线性扫描解决连通检测，贪心策略指导决策，重力下落模拟物理效果。但将这些简单组件组合起来形成流畅的游戏体验，需要对数据结构和算法有清晰的理解。通过Java实现，我们不仅掌握了游戏开发的基础，也加深了对二维数组操作和状态模拟的认识。