无法通过图搜索
问题描述:
试图在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
该代码似乎是正确的。我敢肯定,我忽略了一件小事。
答
我能够通过添加另一构件到节点类,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);
}
解决此类问题的正确工具是您的调试器。在*堆栈溢出问题之前,您应该逐行执行您的代码。如需更多帮助,请阅读[如何调试小程序(由Eric Lippert撰写)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/)。至少,您应该\编辑您的问题,以包含一个[最小,完整和可验证](http://*.com/help/mcve)示例,该示例再现了您的问题,以及您在调试器。 –
听起来像你可能已经使用调试器来获得'k'的意外值。下一步将是在'k - '上放置一个断点,并寻找'k'减少且不应该出现的情况。 – user4581301