a******e
发帖数: 710 | 1 题目如下：
Given a 2D array of black and white entries representing a maze with
designated entrance and exit points, find a path from the entrance to the
exit, if one exists.
答案是
class Coordinate {
public:
int x, y;
const bool operator==(const Coordinate &that) const {
return (x == that.x && y == that.y);
}
};
bool is_feasible(const Coordinate &cur, const vector> &maze) {
return cur.x >= 0 && cur.x < maze.size() &&
cur.y >= 0 && cur.y < maze[cur.x].size() &&
maze[cur.x][cur.y] == 0;
}
bool search_maze_helper(vector> &maze, const Coordinate &cur,
const Coordinate &e, vector &path) {
if (cur == e) {
return true;
}
const array, 4> = {0, 1, 0, -1, 1, 0, -1, 0};
for (const array &s : shift) {
Coordinate next{cur.x + s[0], cur.y + s[1]};
if (is_feasible(next, maze)) {
maze[next.x][next.y] = 1;
path.emplace_back(next);
if (search_maze_helper(maze, next, e, path)) {
return true;
}
path.pop_back();
// maze[next.x][next.y] = 0; //这句在答案中没有，是不是答案错了？
}
}
return true;
}
vector search_maze(vector> maze, const Coordinate &s
, const Coordinate &e) {
vector path;
maze[s.x][s.y] = 1;
path.emplace_back(s);
if (search_maze_helper(maze, s, e, path)==false) {
path.pop_back();
}
return path;
}
其中有一个地方我觉得答案不正确并注释出来了，请问我想的对不对？多谢~ | b*****a
发帖数: 70 | 2 I don't think there is any problem since the problem is only looking for "a"
path from source to destination. If you unset the visited notation, the
algorithm will become much slower. Therefore, I think this implementation is
pretty good in my opinion.
P.S. I think you can always ask the authors questions by emailing them. From
their amazon reviews, it seems they are really responsive and knowledgeable
. | a******e
发帖数: 710 | 3 多谢回复！
经大神指点，我才发现原来对这个问题的思考不够深入。
我原来做这种题只知道一味的恢复递归调用之前的状态。
如果这道题还是恢复状态的话，就会造成对一个点重复的搜索。
如果不恢复状态，这个解法就类似于DP with memory了，不知道我理解的是否正确？
多谢~~
a"
is
From
knowledgeable
【在 b*****a 的大作中提到】
: I don't think there is any problem since the problem is only looking for "a"
: path from source to destination. If you unset the visited notation, the
: algorithm will become much slower. Therefore, I think this implementation is
: pretty good in my opinion.
: P.S. I think you can always ask the authors questions by emailing them. From
: their amazon reviews, it seems they are really responsive and knowledgeable
: .
| J****3
发帖数: 427 | 4 加上楼主那句 是回溯构建所有能到达终点的路径？
这种只找 ‘a’ path 的DFS下去就行？没必要回溯？不知道理解对不对 | b*****a
发帖数: 70 | 5 I think you mean recursion with memorization (i.e., DP). I probably won't
call it DP, however, since they all use recursion, its feeling is similar
and I agree what you said :)
【在 a******e 的大作中提到】
: 多谢回复！
: 经大神指点，我才发现原来对这个问题的思考不够深入。
: 我原来做这种题只知道一味的恢复递归调用之前的状态。
: 如果这道题还是恢复状态的话，就会造成对一个点重复的搜索。
: 如果不恢复状态，这个解法就类似于DP with memory了，不知道我理解的是否正确？
: 多谢~~
:
: a"
: is
: From
|
|
