我有一个非常困难的项目，我必须为我的大学做。它是一个身体扫描仪，其概念基于1993 年 ACM 决赛的问题 H，扫描仪。
请查看图片以了解问题。
所以，就我们而言。我需要您的帮助来制作一种算法，该算法可以获取数据输入的数字并根据这些数字生成一个表格（在我们的例子中为 10x15）。前 10 个数字表示每行 (1) 中非白色单元格的数量。接下来的 24 是从左到右对角线 (2) 中非白色单元格的数量。接下来的 15 个是每列中非白色单元格的数量 (3)，最后 24 个是从右到左对角线中的非白色单元格的数量 (4)。我一直在尝试想出一种算法来组合所有这些数据并创建数组，但没有结果。
我太喜欢逻辑练习了，不能让这个通过我，所以我花了一段时间在 javascript 中制定一个解决方案。首先，代码创建一个表格来显示结果并用作数据结构，然后有四个函数用于检查水平线、垂直线和两条对角线。这四个函数中的每一个都具有相同的形式：在每一行上，找到未设置值的空闲单元格的数量，以及包含主体的完整单元格的数量。然后，如果有足够的空闲单元格用于包含身体的剩余单元格，则填充这些单元格。最后，如果没有包含正文的剩余单元格，则将剩余的空闲单元格标记为空。
之后，剩下的就是冲洗并重复。每次运行四个函数中的一个时，都会有更多的单元格被标记为已满或为空，从而使下一个函数能够在更多约束条件下执行相同的操作。所有四个函数的三遍解决了您的示例问题，尽管更大和更复杂的形状肯定需要更多，如果它们可以解决的话。我可以很容易地想象这种方法无法解决的形状。
function create(rows, cols) {
var table = document.createElement('table');
for (var i = 0; i < rows; i++) {
var row = table.insertRow(-1);
for (var k = 0; k < cols; k++) {
var cell = row.insertCell(-1);
cell.value = null;
cell.innerHTML = ' ';
cell.style.width = '15px';
cell.style.backgroundColor = '#cccccc';
}
}
table.maxrow = rows - 1;
table.maxcol = cols - 1;
document.body.appendChild(table);
return table;
}
function checkRows(table, rows) {
for (var i = 0; i < rows.length; i++) {
var free = 0;
var full = 0;
for (var k = 0; k <= table.maxcol; k++) {
if (table.rows[i].cells[k].value == null) {
free++;
} else if (table.rows[i].cells[k].value == 1) {
full++;
}
}
if (free == 0) {
continue;
} else if (rows[i] - full == free) {
for (var k = 0; k <= table.maxcol; k++) {
if (table.rows[i].cells[k].value == null) {
table.rows[i].cells[k].style.backgroundColor = '#ffcccc';
table.rows[i].cells[k].value = 1;
}
}
} else if (rows[i] - full == 0) {
for (var k = 0; k <= table.maxcol; k++) {
if (table.rows[i].cells[k].value == null) {
table.rows[i].cells[k].style.backgroundColor = '#ccffcc';
table.rows[i].cells[k].value = 0;
}
}
}
}
}
function checkCols(table, cols) {
for (var i = 0; i < cols.length; i++) {
var free = 0;
var full = 0;
for (var k = 0; k <= table.maxrow; k++) {
if (table.rows[k].cells[i].value == null) {
free++;
} else if (table.rows[k].cells[i].value == 1) {
full++;
}
}
if (free == 0) {
continue;
} else if (cols[i] - full == free) {
for (var k = 0; k <= table.maxrow; k++) {
if (table.rows[k].cells[i].value == null) {
table.rows[k].cells[i].style.backgroundColor = '#ffcccc';
table.rows[k].cells[i].value = 1;
}
}
} else if (cols[i] - full == 0) {
for (var k = 0; k <= table.maxrow; k++) {
if (table.rows[k].cells[i].value == null) {
table.rows[k].cells[i].style.backgroundColor = '#ccffcc';
table.rows[k].cells[i].value = 0;
}
}
}
}
}
function checkDiagonals1(table, diagonals) {
for (var i = 0; i < diagonals.length; i++) {
var row = i;
var col = 0;
if (i > table.maxrow) {
row = table.maxrow;
col = i - row;
}
var free = 0;
var full = 0;
for (var k = 0; k <= row && col + k <= table.maxcol; k++) {
if (table.rows[row - k].cells[col + k].value == null) {
free++;
} else if (table.rows[row - k].cells[col + k].value == 1) {
full++;
}
}
if (free == 0) {
continue;
} else if (diagonals[i] - full == free) {
for (var k = 0; k <= row && col + k <= table.maxcol; k++) {
if (table.rows[row - k].cells[col + k].value == null) {
table.rows[row - k].cells[col + k].style.backgroundColor = '#ffcccc';
table.rows[row - k].cells[col + k].value = 1;
}
}
} else if (diagonals[i] - full == 0) {
for (var k = 0; k <= row && col + k <= table.maxcol; k++) {
if (table.rows[row - k].cells[col + k].value == null) {
table.rows[row - k].cells[col + k].style.backgroundColor = '#ccffcc';
table.rows[row - k].cells[col + k].value = 0;
}
}
}
}
}
function checkDiagonals2(table, diagonals) {
for (var i = 0; i < diagonals.length; i++) {
var row = table.maxrow;
var col = i;
if (i > table.maxcol) {
row = table.maxrow - i + table.maxcol;
col = table.maxcol;
}
var free = 0;
var full = 0;
for (var k = 0; k <= row && k <= col; k++) {
if (table.rows[row - k].cells[col - k].value == null) {
free++;
} else if (table.rows[row - k].cells[col - k].value == 1) {
full++;
}
}
if (free == 0) {
continue;
} else if (diagonals[i] - full == free) {
for (var k = 0; k <= row && k <= col; k++) {
if (table.rows[row - k].cells[col - k].value == null) {
table.rows[row - k].cells[col - k].style.backgroundColor = '#ffcccc';
table.rows[row - k].cells[col - k].value = 1;
}
}
} else if (diagonals[i] - full == 0) {
for (var k = 0; k <= row && k <= col; k++) {
if (table.rows[row - k].cells[col - k].value == null) {
table.rows[row - k].cells[col - k].style.backgroundColor = '#ccffcc';
table.rows[row - k].cells[col - k].value = 0;
}
}
}
}
}
var rows = new Array(10, 10, 6, 4, 6, 8, 13, 15, 11, 6);
var cols = new Array(2, 4, 5, 5, 7, 6, 7, 10, 10, 10, 7, 3, 3, 5, 5);
var diagonals1 = new Array(0, 1, 2, 2, 2, 2, 4, 5, 5, 6, 7, 6, 5, 6, 6, 5, 5, 6, 6, 3, 2, 2, 1, 0);
var diagonals2 = new Array(0, 0, 1, 3, 4, 4, 4, 4, 3, 4, 5, 7, 8, 8, 9, 9, 6, 4, 4, 2, 0, 0, 0, 0);
var table = create(rows.length, cols.length);
checkRows(table, rows);
checkCols(table, cols);
checkDiagonals1(table, diagonals1);
checkDiagonals2(table, diagonals2);
The general answer to this is that it's like a CAT scan and there is a very nice introductory article Saving lives: the mathematics of tomography that gives a light overview of how it's really done (invert the Radon transform using a Fourier transform).
On the other hand, I find it hard to believe that a programming competition expected you to do that, so I suspect that for simple cases one can treat this as a constraint satisfaction problem, so you can try searching the space of possible solutions and cutting off the search wherever the solution doesn't match the constraints. Depending on how you structure your search and how efficiently you check your constraints, this might be efficient enough for small problems.
好吧，线条和列很容易。它们只是 x 或 y 坐标。
游戏正在检测对角线。
如果你想一想，这并不是特别难。
考虑：
a
ba
cba
dcba
edcba
通过一点研究，您可以看到单元格和对角线之间的关系。
但是桌子的另一半呢？
考虑一下：
a
ba
cba
dcba
-----
edcba
fedcb
gfedc
hgfed
ihgfe
-----
ihgf
ihg
ih
i
线条是表格的边界，但您可以看到对角线只是从表格“外部”突出。因此，一旦您可以解决基本情况（对于桌子上的那些），可以说“让您的桌子更大”。例如，要找出右上角“a”的对角线，您最终可能会得到“对角线数”，哦，-4 或 -5（类似的东西）。只需将其与其余部分一起移回（即添加 4 或 5），这会将“a”对角线移动到 0（或任何您想要的位置）。
但归根结底，对角线和其他行列式只是基于坐标的函数。算出这些方程式，你就完成了。