旅行網格迴文掌

我一直在嘗試解決這個問題，現在已經有一段時間了，除了天真的解決方案之外，還沒有能夠拿出任何東西。基本上，我得到一個大小爲N的字符網格，在這個字符網格中，當只向下行進時，我必須找到從左上角到右上角的不同路徑的數量，而這個路徑只能向下行進，並且向右返回迴文。旅行網格迴文掌

這裏是一個網格的示例：

ABCD

BXZX

CDXB

WCBA

有12個迴文在此網格諸如「ABXZXBA」。我的解決方案是遍歷網格中的所有路徑，並通過爲前N個字符保留一個字符堆棧併爲每個下一個N個字符彈出每個字符並檢查它們是否相同來檢查該字符串是否爲迴文。當N變得太大並且我不知道如何繼續時，該解決方案超時。任何psuedocode或建議將不勝感激。

來源

2015-04-05 Prash Som

對於每一個字符C在網格中，搜索以C爲中心字符的迴文。請注意，會有像'... xyzCzyx ...'這樣的迴文，並且像'... xyzCCzyx ...' – salva 2015-04-06 07:26:06

如果只允許「向右和向右」，如何才能到達「右上角」「？ – 2015-04-06 16:59:14

只是一個理論 - 我還沒有嘗試過的工作了沒有代碼：

你可以在左上角和右下角的啓動和保持同步的路徑。由於它是一個迴文，所以在從底部到頂部的路徑中需要使用相同的字母。

每次查找路徑中的下一步時，請檢查以確保在反向步驟中有匹配的字母。

反向步驟的可用路徑可能會進一步受到限制，因爲它無法到達左側或高於前進步驟。

停止路徑會合時，由於它們可能最終位於同一個網格位置（奇數行），或者它們可能會遇到（甚至是多行），所以停止。

回溯跟蹤和堆棧保留可能有點複雜，因爲您必須考慮（可能）反向步驟的幾種選擇，但它應該減少可能性的數量。考慮到這一點可能會更好，因爲前進和後退路徑的每一步都會爲您提供一個新的（更小的）網格來檢查迴文。

來源

2015-04-06 01:38:09

像這樣？

（至少它，如果路徑沒有形成迴文或超出範圍/同步停止。）

JavaScript代碼：

function f(m){ 

    var stack = [[0,0,m.length - 1,m.length - 1,""]], 
     count = 0; 

    while(stack.length > 0){ 

    var next = stack.pop(), 
     y = next[0], 
     x = next[1], 
     yr = next[2] 
     xr = next[3]; 

    if (y - yr > 0 || x - xr > 0){ 
     continue; 
    } else if (m[y][x] != m[yr][xr]){ 
     continue; 
    } else if (y == yr && x == xr){ 
     count++; 
    } else { 
     stack.push([y + 1,x,yr - 1,xr]); 
     stack.push([y + 1,x,yr,xr - 1]); 
     stack.push([y,x + 1,yr - 1,xr]); 
     stack.push([y,x + 1,yr,xr - 1]); 
    } 
    } 

    return count; 
}

輸出：

var t = [["A","B","C","D"] 
     ,["B","X","Z","X"] 
     ,["C","D","X","B"] 
     ,["W","C","B","A"]]; 

console.log(f(t)); 

12

來源

2015-04-06 20:50:55

旅行網格迴文掌

回答

相關問題