解決Kaeru跳躍（ACM ICPC日本）

Question

這是ACM ICPC日本。鏈接here解釋了問題和圖表。

任何人都可以幫我解決方案的邏輯？我只知道在這裏沒有通過我的天真的強力方法。

Answer 1

蠻力似乎確實是解決方案：http://mainly-coding.blogspot.dk/2010/09/m-judge-10156-kaeru-jump.html。你只需要進一步優化你的解決方案。

你可以用動態編程來做n2^n，但是這會佔用太多的內存。根據維基百科的說法，因爲立方圖上的哈密爾頓路徑可以按照1.25^n這樣的東西求解，所以也可能有更快的算法。

我不認爲這是一個好問題，因爲它不是很明顯，蠻力比3^30快，但很多人會嘗試並取得成功。你可以證明，大多數情況下你只有一個選擇讓你下一次跳躍，所以跑步時間低於3^n，但我不知道該怎麼做。

Answer 2

下面是Javascript中的蠻力解決方案。你可以直接從代碼片段中運行它。使用具有30片樹葉的10x10樣本網格，該算法將訪問搜索樹的11 683個節點。或者以不同的順序查看可能的跳躍，我有26 269次訪問。像@ThomasAhle預計，這是低於3 （205 891 132 094 649）。

進一步改進的一種方法是檢測樹葉變得無法到達，這可能導致較早的回溯。如果兩片葉片變成單向行程，則相同：這不能被解決，因此算法一旦檢測到這種情況就會回溯。

我沒有嘗試任何這些優化，因爲下面的實現在我運行Firefox的極其緩慢的筆記本電腦上僅在0.1秒內找到了10x10示例的解決方案。

var directionLetters = 'URDL'; 
 

 
function parseInput(input) { 
 
    // Get input elements and return error message when not valid 
 
    var sp = input.trim().split(/\s+/g); 
 
    var h = parseInt(sp.shift()); 
 
    var w = parseInt(sp.shift()); 
 
    if (isNaN(w) || isNaN(h)) return "Invalid width or height"; 
 
    var grid = sp.join(''); 
 
    if (grid.length != w*h) return "Wrong amount of cells"; 
 
    var badChars = grid.replace(/[\.oURDL]/g, ''); 
 
    if (badChars.length) return "Bad cell characters ('" + badChars + "')"; 
 
    
 
    // Turn grid into double linked list of leaves, in horizontal and vertical 
 
    // directions. 
 
    var count = 0; 
 
    var up = []; 
 
    for (var col = 0; col < w; col++) { 
 
     up[col] = null; 
 
    } 
 
    for (var line = 0; line < h; line++) { 
 
     var left = null; 
 
     for (var col = 0; col < w; col++) { 
 
      var ch = grid[line*w+col]; 
 
      if (ch !== '.') { 
 
       leaf = { 
 
        row: line, // not really needed 
 
        col: col, // not really needed 
 
        neighbor: [ 
 
         up[col], 
 
         null, 
 
         null, 
 
         left 
 
        ] 
 
       }; 
 
       if (left) { 
 
        left.neighbor[1] = leaf; 
 
       } 
 
       if (up[col]) { 
 
        up[col].neighbor[2] = leaf; 
 
       } 
 
       left = leaf; 
 
       up[col] = leaf; 
 
       if (directionLetters.indexOf(ch) !== -1) { 
 
        direction = directionLetters.indexOf(ch); 
 
        currentLeaf = leaf; 
 
       } 
 
       count++; 
 
      } 
 
     } 
 
    } 
 
    return { 
 
     count: count, 
 
     currentLeaf: currentLeaf, 
 
     direction: direction 
 
    }; 
 
} 
 

 
function getValidJumps(leaves) { 
 
    var jumps = []; 
 
    for (var direction = 0; direction < 4; direction++) { // four directions 
 
     if ((direction^leaves.direction) !== 2 // cannot be opposite 
 
       && leaves.currentLeaf.neighbor[direction]) { 
 
      // valid jump 
 
      jumps.push({ 
 
       count: leaves.count - 1, 
 
       currentLeaf: leaves.currentLeaf.neighbor[direction], 
 
       direction: direction 
 
      }); 
 
     } 
 
    } 
 
    return jumps; 
 
} 
 

 
function removeLeaf(leaf) { 
 
    // adapt double linked lists to exclude this leaf 
 
    for (var i = 0; i < 4; i++) { 
 
     if (leaf.neighbor[i]) { 
 
      leaf.neighbor[i].neighbor[i^2] = leaf.neighbor[i^2]; 
 
     } 
 
    } 
 
} 
 

 
function restoreLeaf(leaf) { 
 
    // adapt double linked lists to include this leaf 
 
    for (var i = 0; i < 4; i++) { 
 
     if (leaf.neighbor[i]) { 
 
      leaf.neighbor[i].neighbor[i^2] = leaf; 
 
     } 
 
    } 
 
} 
 

 
// Main recursive algorithm: 
 
function searchPath(leaves) { 
 
    if (leaves.count <= 1) return ''; // found a solution 
 
    var jumps = getValidJumps(leaves); 
 
    removeLeaf(leaves.currentLeaf); 
 
    for (var j = 0; j < jumps.length; j++) { 
 
     var path = searchPath(jumps[j]); 
 
     if (path !== false) return directionLetters[jumps[j].direction] + path; 
 
    }; 
 
    restoreLeaf(leaves.currentLeaf); 
 
    return false; // no solution 
 
} 
 

 
// I/O 
 
document.getElementById('solve').onclick = function() { 
 
    var leaves = parseInput(document.getElementById('input').value); 
 
    document.getElementById('output').textContent = 
 
     typeof leaves == "string" // error in input? 
 
      ? leaves : searchPath(leaves); 
 
} 
 

 
document.getElementById('input').oninput = function() { 
 
    document.getElementById('output').textContent = ''; // clear 
 
}

<textarea id="input" rows=11 cols=20 style="float:left"> 
 
10 10 
 
.o....o... 
 
o.oo...... 
 
..oo..oo.. 
 
..o....... 
 
..oo..oo.. 
 
..o...o.o. 
 
o..U.o.... 
 
oo......oo 
 
oo........ 
 
oo..oo.... 
 
</textarea> 
 
<button id="solve">Solve</button> 
 
<h4>Solution:</h4> 
 
<div id="output"></div>