您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

連連看消除演算法：分治法實現零/一/兩拐點連通判定完整解析

編輯：Java 綜合教學

一、問題定義

給定二維網格，兩個相同圖案座標 (x1,y1)、(x2,y2)，判斷能否用最多兩個彎折 (三條線段) 的正交折線連通，且路徑上全為空格 (0) (不含端點)。

二、分治策略：大問題拆解為三個子問題

零拐點：同一直線 (同行/同列) 且中間全空。
一拐點：存在一個轉角點 D，使 A→D、D→B 均為零拐點通路，且 D 為空。
兩拐點：從 A 向四方向延伸，尋找空格 C，使 C→B 為一拐點通路。

遞歸結構：兩拐點 → 一拐點 → 零拐點，層層化簡。

三、核心判定函數 (Java 實作)

public class LinkGameSolver {
    private final int[][] grid; // 0=空, >0=圖案ID
    private final int rows, cols;

    public LinkGameSolver(int[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
    }

    /** 入口：判斷兩點可否消除 */
    public boolean canLink(int x1, int y1, int x2, int y2) {
        if (x1 == x2 && y1 == y2) return false; // 同點
        if (grid[x1][y1] != grid[x2][y2]) return false; // 圖案不同
        return zeroTurn(x1, y1, x2, y2) ||
               oneTurn(x1, y1, x2, y2) ||
               twoTurn(x1, y1, x2, y2);
    }

    /** 零拐點：同行/同列且中間全 0 */
    private boolean zeroTurn(int x1, int y1, int x2, int y2) {
        if (x1 != x2 && y1 != y2) return false; // 不在同一直線
        if (x1 == x2) { // 同行
            int minY = Math.min(y1, y2), maxY = Math.max(y1, y2);
            for (int y = minY + 1; y < maxY; y++)
                if (grid[x1][y] != 0) return false;
        } else { // 同列
            int minX = Math.min(x1, x2), maxX = Math.max(x1, x2);
            for (int x = minX + 1; x < maxX; x++)
                if (grid[x][y1] != 0) return false;
        }
        return true;
    }

    /** 一拐點：兩種可能轉角 (x1,y2) 或 (x2,y1) 均為空且兩段零拐點通 */
    private boolean oneTurn(int x1, int y1, int x2, int y2) {
        if (x1 == x2 || y1 == y2) return false; // 已被零拐點覆蓋
        // 轉角 D1 = (x1, y2)
        if (grid[x1][y2] == 0 && zeroTurn(x1, y1, x1, y2) && zeroTurn(x1, y2, x2, y2))
            return true;
        // 轉角 D2 = (x2, y1)
        if (grid[x2][y1] == 0 && zeroTurn(x1, y1, x2, y1) && zeroTurn(x2, y1, x2, y2))
            return true;
        return false;
    }

    /** 兩拐點：從 A 向四方向掃描空格 C，若 C→B 為一拐點則成功 */
    private boolean twoTurn(int x1, int y1, int x2, int y2) {
        // 向上
        for (int x = x1 - 1; x >= 0; x--) {
            if (grid[x][y1] != 0) break;
            if (oneTurn(x, y1, x2, y2)) return true;
        }
        // 向下
        for (int x = x1 + 1; x < rows; x++) {
            if (grid[x][y1] != 0) break;
            if (oneTurn(x, y1, x2, y2)) return true;
        }
        // 向左
        for (int y = y1 - 1; y >= 0; y--) {
            if (grid[x1][y] != 0) break;
            if (oneTurn(x1, y, x2, y2)) return true;
        }
        // 向右
        for (int y = y1 + 1; y < cols; y++) {
            if (grid[x1][y] != 0) break;
            if (oneTurn(x1, y, x2, y2)) return true;
        }
        return false;
    }
}

四、複雜度分析

指標	複雜度	說明
時間	O(max(R,C))	最差掃描整行/整列，R=行數, C=列數。實際遠小於理論上限。
空間	O(1)	僅使用常數額外變數，無遞歸棧溢位風險。

優化方向：預計算每行/每列的「下一障礙物」索引，將掃描降為 O(1) 查詢；或改用 BFS 最短路徑判定彎折數 (通用但常數較大)。

五、擴展：外圍虛擬邊界技巧

在陣列四周各擴一圈 0，可統一處理「延伸至邊界再轉角」的情況，省去邊界判斷 if (x==0) ...，程式碼更簡潔。

六、完整測試範例

public static void main(String[] args) {
    int[][] board = {
        {0,0,0,0,0},
        {0,1,0,2,0},
        {0,0,0,0,0},
        {0,3,0,1,0},
        {0,0,0,0,0}
    };
    LinkGameSolver solver = new LinkGameSolver(board);
    // (1,1) 與 (3,3) 都是 1，中間可通
    System.out.println(solver.canLink(1, 1, 3, 3)); // true
    // (1,3)=2 與 (3,1)=3 不同
    System.out.println(solver.canLink(1, 3, 3, 1)); // false
}