グラフを検索する際に問題が発生しました

Question

HackerrankでCount Luck問題を解決しようとしています。目的はノードの森を経由してターゲット*へのパスを見つけ、ターゲットパス上のノード数のうちkが推測され、有効な隣接パスが2つ以上あると仮定して、その推測が正しいかどうかを判断する必要があります。それが正しい場合は "Impressed"、それ以外の場合は "Oops！"

プレイヤーは'M'で始まり、ターゲットへの完全なパスは1つしかありません。プレーヤーはノードXを歩くことはできません。有効なパスは.個のノードで構成されていますが、そこを歩くことしかできません。また、プレイヤーは上下左右にしか移動できません。

ここでは4と11の寸法である森の例だと3推測である：

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

有効な1以上を有する目標経路上の3つのノードがあるので、これは「感動」印刷隣接するパス。すなわち、（2,9）、（0,5）、（3,3）となる。推測は正しい。

私のアプローチは、深さの最初の検索を行い、各ノードに対して、隣接するノードのそれぞれを分析し、それらが有効かどうかを判断することでした。 1つ以上の有効なノード（行き止まりにつながるターゲット+ノードにつながるノード）がある場合、kを減らします。目標値kがゼロであることが分かると、「印象づけ済み」と表示されます。それ以外の場合は「おっと！」と表示されます。

#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'; 
    } 
} 

このコードは、上記のテストケースのために動作しますが、いくつか他の人のために失敗しました。たとえば、この1つです。 「おっと！」と表示されます。 「印象づけ」を印刷することになっているとき。 kが0の代わりに-2にデクリメントされることがわかります。

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

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