Проект: Body Scanner, ACM 1993
У меня есть довольно сложный проект, который я должен сделать для своего университета. Это сканер тела, и его концепция основана на проблеме ACM Final 1993 года H, Сканер.
http://i43.tinypic.com/2uhms69.jpg
Пожалуйста, смотрите изображение, чтобы понять проблему.
Итак, к нашей точке. Мне нужна ваша помощь для создания алгоритма, который получает числа для ввода данных и создает таблицу (10x15 в нашем случае) на основе этих чисел. Первые 10 чисел представляют количество не белых клеток в каждой строке (1). Следующие 24 числа небелых клеток в диагонали слева направо (2). Следующие 15 - количество не белых клеток в каждом столбце (3), а последние 24 - количество не белых клеток в диагонали справа налево (4). Я пытался придумать алгоритм, который объединяет все эти данные и создает массив, но безрезультатно.
3 ответа
Мне слишком нравятся логические упражнения, чтобы пропустить это, и я потратил некоторое время на разработку решения в 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);
Ну, строки и столбцы просты. Они просто координаты х или у.
Игра обнаруживает диагонали.
И это не супер сложно, если немного подумать.
Рассматривать:
a
ba
cba
dcba
edcba
После небольшого изучения вы можете увидеть связь между клетками и диагональю.
Но как насчет другой половины стола?
Учти это:
a
ba
cba
dcba
-----
edcba
fedcb
gfedc
hgfed
ihgfe
-----
ihgf
ihg
ih
i
Линии являются границами таблицы, но вы можете видеть, что диагонали просто проецируются "снаружи" таблицы. Поэтому, как только вы сможете решить основной случай (для тех, которые на столе), просто, так сказать, "сделайте ваш стол больше". Например, чтобы узнать диагональ "а" в верхнем правом углу, вы можете в конечном итоге получить "диагональное число", о, -4 или -5 (что-то в этом роде). Просто сдвиньте его назад (т.е. добавьте 4 или 5) вместе с остальными, и это сместит диагональ "а" в 0 (или куда вы хотите).
Но в конце диагональ и другие детерминанты являются просто функциями, основанными на координатах. Разработайте эти уравнения, и все готово.
Общий ответ на это таков, что это похоже на CAT-сканирование, и есть очень хорошая вводная статья " Спасение жизней": математическая томография, которая дает легкий обзор того, как это действительно делается ( инвертировать преобразование Радона, используя преобразование Фурье).
С другой стороны, мне трудно поверить, что соревнование по программированию ожидало, что вы это сделаете, поэтому я подозреваю, что для простых случаев это можно рассматривать как проблему удовлетворения ограничений, поэтому вы можете попробовать поискать пространство возможных решений и сократить от поиска там, где решение не соответствует ограничениям. В зависимости от того, как вы структурируете свой поиск и насколько эффективно вы проверяете свои ограничения, это может быть достаточно эффективно для небольших проблем.