無法通過圖搜索

Question

試圖在Hackerrank上執行Count Luck問題。任務是找到一個通過節點森林的路徑到目標*，並給出猜測目標路徑上具有多於1個有效相鄰路徑的節點數k我必須確定該猜測是否正確。如果它是正確的打印「印象深刻」，否則「哎呀！」。

玩家從'M'開始，目標只有1條完整路徑。玩家不能穿過X節點。有效路徑由.節點組成，您只能通過那裏走過。另外，玩家只能向上，向下，向左或向右移動。

這裏的森林裏4和11的尺寸和3的例子猜測：

4 11 
.X.X......X 
.X*.X.XXX.X 
.XX.X.XM... 
......XXXX. 
3 

「印象深刻」，因爲有超過1有效的目標路徑上三個節點此打印相鄰的路徑。也就是說，在（2,9），（0,5）和（3,3）。猜測是正確的。

我的方法是進行深度優先搜索，併爲每個節點分析每個相鄰節點並確定它們是否有效。如果有超過1個有效節點（通往目標+節點的節點導致死衚衕），那麼我們遞減k。如果當我們發現目標k爲零時，我們打印「Impressed」，否則「Oops！」。

#include <vector> 
#include <stack> 
#include <iostream> 
#include <algorithm> 
#include <queue> 
using namespace std; 

struct node { 
    int x, y; 

    node() = default; 
    node(int x, int y) : x(x), y(y) 
    {} 
}; 

string makeGuess(vector<string> const& forest, int n, int m, node player, int k) { 
    vector<vector<bool>> visited(n, vector<bool>(m)); 

    auto isUnvisitedNode = [&](node v) 
    {return (0 <= v.x && v.x < n) && (0 <= v.y && v.y < m) && !visited[v.x][v.y];}; 

    std::stack<node> s; 
    s.push(player); 

    while (!s.empty()) { 
    node elem = s.top(); 
    s.pop(); 

    if (!isUnvisitedNode(elem)) continue; 
    int x = elem.x; 
    int y = elem.y; 
    visited[x][y] = true; 

    if (forest[x][y] == 'X') continue; 
    if (forest[x][y] == '*') break; 

    std::queue<node> q; 
    q.push(node(x, y-1)); 
    q.push(node(x, y+1)); 
    q.push(node(x-1, y)); 
    q.push(node(x+1, y)); 

    int numberOfPaths = 0; 
    while (!q.empty()) { 
     node v = q.front(); 
     q.pop(); 
     if (isUnvisitedNode(v)) { 
     if (forest[v.x][v.y] == '.' || forest[v.x][v.y] == '*') { 
      numberOfPaths++; 
     } 
     } 
     s.push(v); 
    } 
    if (numberOfPaths > 1) k--; 
    } 

    if (k == 0) 
    return "Impressed"; 
    else 
    return "Oops!"; 
} 

int main() { 
    int n, m, i, j, k, p, t; 
    node player; 

    cin >> t; 
    for (p = 0; p < t; ++p) { 
    cin >> n >> m; 
    vector<string> forest(n); 
    for (i = 0; i < n; ++i) { 
     string str; cin >> str; 
     if ((j = str.find('M')) != string::npos) 
     player = node(i, j); 
     forest[i] = move(str); 
    } 
    cin >> k; 
    cout << makeGuess(forest, n, m, player, k) << '\n'; 
    } 
} 

此代碼適用於上述的測試案例，但失敗了幾個人。例如，這一個。它打印「哎呀！」當它應該打印「印象深刻」。原來k遞減到-2而不是0。

41 41 
.X.XXXXXXXXXXXXXXXXXXX.X.X.X.X.X.X.X.X.X. 
...XXXXXXXXXXXXXXXXXXX................... 
.X..X.X.X.X.X.X.X..XXXX*X.X.X.X.X.X.X.XX. 
.XXXX.X.X.X.X.X.X.XX.X.X.X.X.X.X.X.X.X.X. 
......................................... 
.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX. 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX. 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX. 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
.XX.X.X.X.XX.X.XX.X.X.X.X.X.X.X.X.X.X.X.X 
.X.X.X.X.X.XXX.X.X.X.X.X.X.X.X.X.X.X.X.X. 
X........................................ 
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX. 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
.X.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX.XX 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XMX. 
.X....................................X.. 
..X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX. 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
.X...................................X... 
.XX.X.X.X.X.X.X.X.X.X.X.X.X.X.XX.XX.XXXX. 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX. 
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X. 
......................................... 
294 

該代碼似乎是正確的。我敢肯定，我忽略了一件小事。

Answer 1

我能夠通過添加另一構件到節點類，count，它是倍Hermonie波魔杖從M到*的數量來解決這個。對於所有相鄰的節點，我檢查它們是否是有效的路徑。如果有多條有效路徑，我們將增加所有相鄰節點的count成員，並繼續搜索。最終目標節點將包含答案，我們檢查k == lastNode.count。

std::array<node, 4> arr = {{ 
    node(x, y - 1, last.count), 
    node(x, y + 1, last.count), 
    node(x - 1, y, last.count), 
    node(x + 1, y, last.count) 
}}; 

int count = 0; 
for (auto const& v : arr) { 
    if (isUnvisitedNode(v)) { 
    if (forest[v.x][v.y] == '.' || forest[v.x][v.y] == '*') { 
     count++; 
    } 
    else { 
     visited[v.x][v.y] = true; 
    } 
    } 
} 

for (auto& v : arr) { 
    if (count >= 2) v.count++; 
    if (isUnvisitedNode(v)) s.push(v); 
}