項目：身體掃描儀，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）中非白色單元格的數量，以及右邊至左邊對角線（4）中非白色單元格的數量的最後24個。我一直在想一個結合所有這些數據並創建數組的算法，但沒有結果。

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掃描和存在，讓它是如何真正做（invert the Radon transform using a Fourier transform）光概述一個很不錯的介紹性文章 Saving lives: the mathematics of tomography。另一方面，我發現很難相信編程競賽期望你這樣做，所以我懷疑對於簡單的情況，可以把它當作一個約束滿足問題，所以你可以嘗試搜索空間可能的解決方案，並在解決方案與約束條件不匹配的地方切斷搜索。根據您的搜索結構以及檢查約束條件的效率，這對於小問題可能足夠有效。

Answer 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 = '&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);