有缺陷的棋盘问题 - 寻找伪代码算法（分治）

Question

我需要使用分治设计递归算法" CBCover"，以确定覆盖（如下图所示）的运行时间为O(n^2)（其中n = 2 ^ k）。

CBCover的输入应为（k，a，b），其中k定义了棋盘的大小，（a，b）是缺失字段的坐标。

可能的覆盖范围：

4x4的棋盘缺失（4,1）：

是否有人知道伪代码可能会是什么样子？

- R0MAN

---

欢迎来到SO！所以你只能使用单个“L”三格骨牌进行平铺吗？这个问题似乎有一个更完整的问题陈述。你尝试过解决这个问题并分享你的想法吗？谢谢。 - ggorlen

Answer 1

算法步骤如下：

确定哪个象限缺失了一个格子。将L型方块置于网格中心，使其占据其他三个象限中的每一个象限中的一个格子。现在你有四个象限，每个象限都有一个无法再使用的格子。对这些象限递归求解，应用相同的策略。当当前网格没有可用的格子时（即它是一个由一个不可用的格子组成的1x1网格），递归停止。

描述镶嵌的不同数据结构有多种可能。一种方法是创建一个二维网格，在其中每个单元格得到一个唯一标识形状所属的值。因此，具有相同值的单元格彼此相邻。

上述算法可以从首先为每个单元格分配一个唯一值的网格开始，并在它们必须属于同一形状时将值从一个单元格复制到另一个单元格。

以下是简单JavaScript的实现。它是交互式的，因此您可以通过点击按钮更改输入，并在悬停鼠标时在网格上识别“丢失的字段”：

// Main algorithm:
function tile(k, a, b) {
    let length = 2**k;
    // Create a grid where each cell has a unique value
    let grid = [];
    for (let y = 0; y < length; y++) {
        let row = [];
        for (let x = 0; x < length; x++) {
             row.push(y*length + x); // unique value
        }
        grid.push(row);
    }
    a = a % length;
    b = b % length;
    
    function recur(length, a, b, top, left) {
        if (length == 1) return;
        let half = length / 2;
        let midrow = top + half;
        let midcol = left + half;
        let quadrant = (a >= midrow) * 2 + (b >= midcol);
        let val = -1;
        for (let i = 0; i < 4; i++) {
            let quadTop = i >= 2 ? midrow : top;
            let quadLeft = i % 2 ? midcol : left;
            let row, col;
            if (quadrant == i) {
                row = a;
                col = b;
            } else {
                row = midrow - 1 + (i >> 1);
                col = midcol - 1 + (i % 2);
                // Add this cell to an L-shape
                if (val == -1) val = grid[row][col];
                else grid[row][col] = val; // join with neighboring cell
            }
            recur(half, row, col, quadTop, quadLeft);
        }
    }
    
    recur(length, a, b, 0, 0);
    return grid;
}

// Parameters of the problem
let k, a, b;

// I/O handling:

function solve(newK, newA, newB) {
    if (newK <= 0) return; // grid must be at least 2x2
    k = newK;
    a = newA;
    b = newB;
    let grid = tile(k, a, b);
    display(grid);
}

let table = document.querySelector("table");

function display(grid) {
    table.innerHTML = "";
    for (let y = 0; y < grid.length; y++) {
        let tr = table.insertRow();
        for (let x = 0; x < grid.length; x++) {
            let val = grid[y][x];
            cls = "";
            if (y && val === grid[y-1][x]) cls += " up";
            if (grid[y+1] && val === grid[y+1][x]) cls += " down";
            if (val === grid[y][x-1]) cls += " left";
            if (val === grid[y][x+1]) cls += " right";
            if (cls === "") cls = "gap";
            tr.insertCell().className = cls.trim();
        }
    }
}

// Allow user to select gap with a click on a cell:
table.addEventListener("mousemove", (e) => {
    let td = e.target;
    if (td.tagName !== "TD") return;
    solve(k, td.parentNode.rowIndex, td.cellIndex);
});

// Allow user to change the size of the grid:
document.querySelector("#dbl").addEventListener("click", () => solve(k+1, a, b));
document.querySelector("#hlf").addEventListener("click", () => solve(k-1, a, b));

// Create, solve and display initial grid
solve(2, 0, 0);

table { border-collapse: collapse }
td { border: 1px solid; width: 10px; height: 10px }
.gap { background: silver }
.up { border-top-color: transparent }
.down { border-bottom-color: transparent }
.left { border-left-color: transparent }
.right { border-right-color: transparent }

<button id="dbl">Increase size</button><button id="hlf">Decrease size</button><br><br>
<table></table><br>

- trincot