私は自分の大学のために作らなければならない非常に難しいプロジェクトを持っています。これはボディスキャナーであり、コンセプトは1993年のACMファイナルの問題H 、スキャナーに基づいています。
問題を理解するために写真を見てください。
だから、私たちのポイントに。データ入力用の数値を取得し、これらの数値に基づいてテーブル（この場合は10x15）を生成するアルゴリズムを作成するためにあなたの助けが必要です。最初の10個の数字は、すべての行の非白血球の数を表します（1）。次の24は、左から右の対角線にある非白血球の数です（2）。次の15は、すべての列の非白血球の数（3）であり、最後の24は、右から左の対角線の非白血球の数（4）です。私はこれらすべてのデータを組み合わせて配列を作成するアルゴリズムを考えようとしてきましたが、結果はありません。
行と列は簡単です。それらは単なる 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 (または必要な場所) に移動します。
しかし、結局のところ、対角線やその他の決定要因は、座標に基づく関数にすぎません。これらの方程式を計算すると、完了です。
私は論理的な演習が好きすぎて、これをやり過ごすことができませんでした。最初に、コードは結果を表示し、データ構造として機能するテーブルを作成します。次に、水平線、垂直線、および両方の対角線をチェックするための 4 つの関数があります。これら 4 つの関数はそれぞれ同じ形式です。各行で、値が設定されていないフリー セルの数と、本体を含むフル セルの数を見つけます。次に、体を含む残りのセルに対して正確に十分な空きセルがある場合は、それらを埋めます。最後に、ボディを含むセルが残っていない場合は、残りの空きセルを空としてマークします。
後はすすぎを繰り返すだけです。4 つの関数の 1 つが実行されるたびに、より多くのセルが満杯または空としてマークされ、次の関数がより多くの制約を適用して同じことを実行できるようになります。4 つの関数すべてからの 3 つのパスでサンプルの問題が解決されますが、大きくて複雑な形状を解決できる場合は、より多くのパスが必要になることは間違いありません。この方法では解決できない形状は容易に想像できます。
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);
これに対する一般的な答えは、それは CAT スキャンのようなものであり、非常に優れた紹介記事 Saving lives: the mathematics of tomographyがあり、それが実際にどのように行われるかについて簡単な概要を示しているというものです (フーリエ変換を使用してラドン変換を反転します)。
一方で、プログラミング競技会があなたにそれを期待していたとは信じがたいので、単純なケースでは、これを制約充足問題として扱うことができるのではないかと思います。解が制約に一致しない場合はどこでも検索をオフにします。検索をどのように構造化するか、および制約をどれだけ効率的にチェックするかによって、これは小さな問題に対して十分に効率的である可能性があります。