无法通过图搜索

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); 
}