我需要使用分治设计递归算法" CBCover",以确定覆盖(如下图所示)的运行时间为O(n^2)(其中n = 2 ^ k)。
CBCover的输入应为(k,a,b),其中k定义了棋盘的大小,(a,b)是缺失字段的坐标。
可能的覆盖范围:
4x4的棋盘缺失(4,1):
是否有人知道伪代码可能会是什么样子?
我需要使用分治设计递归算法" CBCover",以确定覆盖(如下图所示)的运行时间为O(n^2)(其中n = 2 ^ k)。
CBCover的输入应为(k,a,b),其中k定义了棋盘的大小,(a,b)是缺失字段的坐标。
可能的覆盖范围:
4x4的棋盘缺失(4,1):
是否有人知道伪代码可能会是什么样子?
// 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>