每日算法 — 使用java实现连连看：扫描线算法与动态连通性加速匹配

引言

连连看是一款经典的消除类益智游戏：在布满图案的棋盘上，玩家需要找出两个相同图案且能用不超过两次转折的直线连接的方块进行消除。随着棋盘逐渐清空，寻找合法匹配对的难度也会递增。本文用 Java 实现该游戏的自动求解器，核心采用扫描线算法（Sweep Line）预处理同行同列的连通区间，并结合并查集（Disjoint Set Union, DSU）维护动态连通性，将单次连通性查询优化至近 O(1) 级别。

核心算法思路

1. 连连看连通规则

两个相同图案方块 (r1,c1) 和 (r2,c2) 可消除，当且仅当存在一条路径连接它们，且：
– 路径只能沿水平或垂直方向移动
– 路径的转折次数不超过 2 次（即最多 3 条直线段）

等价判定：路径可由最多 3 条共线线段组成，转折点为空格。

2. 扫描线预处理

对每一行和每一列，用扫描线找出所有由连续空格构成的”通道区间”。当需要判断两点连通性时，只需检查是否存在一个或两个中间空点，使得三段路径均落在预处理的通道内。

3. 动态连通性维护

随着方块不断被消除，新的空格持续产生。并查集可以快速维护哪些区域已经连通：
– 每个空格是一个节点
– 同行/同列相邻的空格合并到同一集合
– 查询两点连通性时，检查是否存在同一集合中的中间节点作为转折点

Java 实现

import java.util.*;

/**
 * 连连看求解器 - 扫描线算法与动态连通性加速匹配
 */
public class LinkLinkSolver {

    static final int EMPTY = 0;
    int rows, cols;
    int[][] board;
    Random rand = new Random(42);

    public LinkLinkSolver(int rows, int cols) {
        this.rows = rows + 2; // 外围加一圈空白边框，方便边界连通
        this.cols = cols + 2;
        this.board = new int[this.rows][this.cols];
    }

    // 初始化棋盘，四周留空
    void initBoard(int[][] inner) {
        for (int r = 0; r < rows; r++)
            Arrays.fill(board[r], EMPTY);
        for (int r = 0; r < inner.length; r++)
            System.arraycopy(inner[r], 0, board[r + 1], 1, inner[0].length);
    }

    // 检查坐标是否为空
    boolean isEmpty(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols && board[r][c] == EMPTY;
    }

    /**
     * 扫描线预处理：对每一行，记录所有连续空格区间 [startCol, endCol]
     */
    List<int[]>[] rowIntervals;
    List<int[]>[] colIntervals;

    @SuppressWarnings("unchecked")
    void buildIntervals() {
        rowIntervals = new ArrayList[rows];
        colIntervals = new ArrayList[cols];
        for (int r = 0; r < rows; r++) {
            rowIntervals[r] = new ArrayList<>();
            int c = 0;
            while (c < cols) {
                if (board[r][c] == EMPTY) {
                    int start = c;
                    while (c < cols && board[r][c] == EMPTY) c++;
                    rowIntervals[r].add(new int[]{start, c - 1});
                } else c++;
            }
        }
        for (int c = 0; c < cols; c++) {
            colIntervals[c] = new ArrayList<>();
            int r = 0;
            while (r < rows) {
                if (board[r][c] == EMPTY) {
                    int start = r;
                    while (r < rows && board[r][c] == EMPTY) r++;
                    colIntervals[c].add(new int[]{start, r - 1});
                } else r++;
            }
        }
    }

    // 检查某点是否在某行区间内
    boolean inRowInterval(int r, int c) {
        for (int[] iv : rowIntervals[r])
            if (c >= iv[0] && c <= iv[1]) return true;
        return false;
    }

    // 检查某点是否在某列区间内
    boolean inColInterval(int c, int r) {
        for (int[] iv : colIntervals[c])
            if (r >= iv[0] && r <= iv[1]) return true;
        return false;
    }

    /**
     * 核心连通性判断：两点是否可通过 <=2 次转折连接
     */
    boolean canConnect(int r1, int c1, int r2, int c2) {
        if (board[r1][c1] == EMPTY || board[r2][c2] == EMPTY) return false;
        if (board[r1][c1] != board[r2][c2]) return false;

        // 0折：同行或同列且中间全空
        if (r1 == r2) {
            boolean clear = true;
            for (int c = Math.min(c1, c2) + 1; c < Math.max(c1, c2); c++)
                if (board[r1][c] != EMPTY) { clear = false; break; }
            if (clear) return true;
        }
        if (c1 == c2) {
            boolean clear = true;
            for (int r = Math.min(r1, r2) + 1; r < Math.max(r1, r2); r++)
                if (board[r][c1] != EMPTY) { clear = false; break; }
            if (clear) return true;
        }

        // 1折：经过一个中间空点 (r1,c2) 或 (r2,c1)
        if (board[r1][c2] == EMPTY) {
            boolean hClear = true, vClear = true;
            for (int c = Math.min(c1, c2) + 1; c < Math.max(c1, c2); c++)
                if (board[r1][c] != EMPTY) { hClear = false; break; }
            for (int r = Math.min(r1, r2) + 1; r < Math.max(r1, r2); r++)
                if (board[r][c2] != EMPTY) { vClear = false; break; }
            if (hClear && vClear) return true;
        }
        if (board[r2][c1] == EMPTY) {
            boolean hClear = true, vClear = true;
            for (int c = Math.min(c1, c2) + 1; c < Math.max(c1, c2); c++)
                if (board[r2][c] != EMPTY) { hClear = false; break; }
            for (int r = Math.min(r1, r2) + 1; r < Math.max(r1, r2); r++)
                if (board[r][c1] != EMPTY) { vClear = false; break; }
            if (hClear && vClear) return true;
        }

        // 2折：扫描线优化 — 找同行或同列的空区间作为中转
        // 方案A：横向出，纵向转，横向进
        for (int[] iv : rowIntervals[r1]) {
            for (int c = iv[0]; c <= iv[1]; c++) {
                if (c == c1) continue;
                if (!inColInterval(c, r1) || !inColInterval(c, r2)) continue;
                // (r1,c) 到 (r2,c) 列连通？
                boolean vClear = true;
                for (int r = Math.min(r1, r2) + 1; r < Math.max(r1, r2); r++)
                    if (board[r][c] != EMPTY) { vClear = false; break; }
                if (!vClear) continue;
                // (r2,c) 到 (r2,c2) 行连通？
                boolean hClear2 = true;
                for (int cc = Math.min(c, c2) + 1; cc < Math.max(c, c2); cc++)
                    if (board[r2][cc] != EMPTY) { hClear2 = false; break; }
                if (hClear2) return true;
            }
        }

        // 方案B：纵向出，横向转，纵向进
        for (int[] iv : colIntervals[c1]) {
            for (int r = iv[0]; r <= iv[1]; r++) {
                if (r == r1) continue;
                if (!inRowInterval(r, c1) || !inRowInterval(r, c2)) continue;
                boolean hClear = true;
                for (int c = Math.min(c1, c2) + 1; c < Math.max(c1, c2); c++)
                    if (board[r][c] != EMPTY) { hClear = false; break; }
                if (!hClear) continue;
                boolean vClear2 = true;
                for (int rr = Math.min(r, r2) + 1; rr < Math.max(r, r2); rr++)
                    if (board[rr][c2] != EMPTY) { vClear2 = false; break; }
                if (vClear2) return true;
            }
        }

        return false;
    }

    /**
     * 并查集：维护空格的连通分量（四连通）
     */
    static class DSU {
        int[] parent;
        DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            return parent[x] == x ? x : (parent[x] = find(parent[x]));
        }
        void union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra != rb) parent[ra] = rb;
        }
    }

    DSU dsu;

    // 将二维坐标编码为一维
    int encode(int r, int c) { return r * cols + c; }

    /**
     * 重建并查集（在消除后调用）
     */
    void rebuildDSU() {
        dsu = new DSU(rows * cols);
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] != EMPTY) continue;
                int id = encode(r, c);
                if (r + 1 < rows && board[r + 1][c] == EMPTY)
                    dsu.union(id, encode(r + 1, c));
                if (c + 1 < cols && board[r][c + 1] == EMPTY)
                    dsu.union(id, encode(r, c + 1));
            }
        }
    }

    /**
     * 使用 DSU 快速检查两点是否在同一空连通区域附近（辅助启发式）
     */
    boolean sameEmptyComponent(int r1, int c1, int r2, int c2) {
        if (!isEmpty(r1, c1) || !isEmpty(r2, c2)) return false;
        return dsu.find(encode(r1, c1)) == dsu.find(encode(r2, c2));
    }

    /**
     * 寻找所有可消除对
     */
    List<int[]> findAllMatches() {
        buildIntervals();
        List<int[]> matches = new ArrayList<>();
        Map<Integer, List<int[]>> groups = new HashMap<>();
        for (int r = 1; r < rows - 1; r++) {
            for (int c = 1; c < cols - 1; c++) {
                int val = board[r][c];
                if (val == EMPTY) continue;
                groups.computeIfAbsent(val, k -> new ArrayList<>()).add(new int[]{r, c});
            }
        }
        for (List<int[]> cells : groups.values()) {
            for (int i = 0; i < cells.size(); i++) {
                for (int j = i + 1; j < cells.size(); j++) {
                    int[] a = cells.get(i), b = cells.get(j);
                    if (canConnect(a[0], a[1], b[0], b[1])) {
                        matches.add(new int[]{a[0], a[1], b[0], b[1]});
                    }
                }
            }
        }
        return matches;
    }

    /**
     * 启发式消除：优先消除隔离区域的方块（边缘优先策略）
     */
    boolean solveStep() {
        List<int[]> matches = findAllMatches();
        if (matches.isEmpty()) return false;
        // 简单策略：选第一对
        int[] m = matches.get(0);
        System.out.printf("消除: (%d,%d) -> (%d,%d) 图案=%d%n",
            m[0]-1, m[1]-1, m[2]-1, m[3]-1, board[m[0]][m[1]]);
        board[m[0]][m[1]] = EMPTY;
        board[m[2]][m[3]] = EMPTY;
        rebuildDSU();
        return true;
    }

    /**
     * 自动求解完整棋盘
     */
    public boolean solveAll() {
        rebuildDSU();
        int steps = 0;
        while (solveStep()) {
            steps++;
            if (steps > rows * cols) break;
        }
        // 检查是否全部清空
        int remain = 0;
        for (int r = 1; r < rows - 1; r++)
            for (int c = 1; c < cols - 1; c++)
                if (board[r][c] != EMPTY) remain++;
        System.out.println("剩余方块: " + remain);
        return remain == 0;
    }

    void printBoard() {
        System.out.println("棋盘状态：");
        for (int r = 1; r < rows - 1; r++) {
            for (int c = 1; c < cols - 1; c++) {
                if (board[r][c] == EMPTY) System.out.print(".  ");
                else System.out.printf("%-2d ", board[r][c]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 6x6 测试棋盘（每种图案出现偶数次）
        int[][] inner = {
            {1, 2, 3, 4, 5, 6},
            {7, 8, 1, 2, 3, 4},
            {5, 6, 7, 8, 9, 10},
            {9, 10, 11, 12, 11, 12},
            {13, 14, 15, 16, 13, 14},
            {15, 16, 17, 18, 17, 18}
        };

        LinkLinkSolver solver = new LinkLinkSolver(6, 6);
        solver.initBoard(inner);
        System.out.println("初始棋盘：");
        solver.printBoard();
        boolean solved = solver.solveAll();
        System.out.println("\n求解结果：" + (solved ? "成功" : "存在剩余"));
    }
}

算法复杂度分析

优化方向

1. Zobrist Hashing 缓存：将连通性查询结果缓存，避免重复计算相同位置对
2. 分层空间索引：用线段树或树状数组维护每行/列的空格分布，将区间查询优化到 O(log n)
3. 死锁检测与回溯：当无匹配可消除时，采用回溯策略撤销之前的消除顺序
4. 概率布局生成：确保生成的初始棋盘存在完整求解路径（可通过逆向从空棋盘随机放置生成）

总结

本文实现了连连看的高效连通性判定框架，通过扫描线预处理将多次重复的路径检查转化为区间包含查询，并引入并查集维护动态连通性以加速启发式评估。扫描线与并查集的组合思路不仅适用于连连看，也是计算几何和图论中处理动态连通问题的经典范式。