プロジェクト：ボディースキャナー、ACM 1993

Question

私は私の大学には非常に難しいプロジェクトがあります。それはボディスキャナであり、コンセプトはスキャナ1993's ACM Final's problem Hに基づいています。

See The Picture Here http://i43.tinypic.com/2uhms69.jpg

問題を理解するためには画像をご参照ください。

だから、私たちの言うとおりです。私は、データ入力のための数値を取得し、これらの数値に基づいてテーブル（私たちの場合は10x15）を生成するアルゴリズムを作成するためにあなたの助けが必要です。最初の10個の数字は、すべての行（1）の非白色細胞の数を表します。次の24は、左から右の対角線（2）の非白色セルの数である。次の15は各列（3）の非白色セルの数であり、最後の24は右から左の対角線（4）の非白色セルの数である。私は、これらのデータをすべて組み合わせて配列を作成するアルゴリズムを考えてみましたが、結果はありませんでした。

Answer 1

まあ、行と列は簡単です。それらはちょうど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（またはどこでも）に移動します。

しかし、結局、対角および他の行列式は、単に座標に基づく関数である。それらの方程式を解きなさい。

Answer 2

一般的な答えは、CATスキャンのようなものです。実際にどのように行われたのかについての光の概要を示す Saving lives: the mathematics of tomographyという素敵な入門記事があります（invert the Radon transform using a Fourier transform）。

一方、プログラミングの競争があなたにそれを期待しているとは考えにくいので、単純なケースではこれを制約満足の問題として扱うことができると思われます。ソリューションが制約条件と一致しない場合はどこでも検索を切り離すことができます。検索の仕組みや制約の確認方法によっては、小さな問題では十分に効率的かもしれません。

Answer 3

私は論理的な練習が大好きで、この1つを私に渡すことができないので、私はしばらくの間、javascriptで解決策を試していました。最初にコードは結果を表示するテーブルを作成し、データ構造として機能するために、水平、垂直、対角線の両方をチェックする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 = '&nbsp;'; 
     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);