class Solution
{
public:
int minStepToReachTarget(vector<int>& KnightPos, vector<int>& TargetPos, int N)
{
ans = -1;
visited.resize(N * N, false);
func(KnightPos[0], KnightPos[1], TargetPos[0], TargetPos[1], N, 0);
return ans;
}
private:
void func(int x, int y, int fr, int fc, int N, int cnt);
int ans;
vector<bool> visited;
};
现在，功能本身：
void func(int x, int y, int fr, int fc, int N, int cnt)
{
if(x > N || y > N || x < 1 || y < 1)
{
return;
}
// Target reached
if(x == fr && y == fc) {
ans = cnt;
return;
}
// Prune futile searches
cnt++;
if (ans >= 0 && ans <= cnt) return;
// Search
int vidx = (y - 1) * N + x - 1;
if (!visited[vidx])
{
visited[vidx] = true;
func(x + 2, y - 1, fr, fc, N, cnt);
func(x + 2, y + 1, fr, fc, N, cnt);
func(x - 1, y + 2, fr, fc, N, cnt);
func(x + 1, y + 2, fr, fc, N, cnt);
func(x - 2, y + 1, fr, fc, N, cnt);
func(x - 2, y - 1, fr, fc, N, cnt);
func(x - 1, y - 2, fr, fc, N, cnt);
func(x + 1, y - 2, fr, fc, N, cnt);
visited[vidx] = false;
}
}
请注意如何访问标志在这里使用。
还要注意上面的几个额外的重要更改：
// Target reached
if(x == fr && y == fc) {
ans = cnt;
return;
}
// Prune futile searches
cnt++;
if (ans >= 0 && ans <= cnt) return;
Your issue is a stack overflow because each level of recursion has no knowledge of what positions have already been checked. Consider this simple example to illustrate:
The knight makes a move of +2,-1, and you make a recursive call to test this new position.
While checking this position, the function will test a move of -2,+1
Do you see the problem? These two cases above will oscillate forever, adding more to the stack as you recurse, until you run out of stack and the operating system terminates your process.
Now, it's not enough to simply remember what the last move is and exclude that, because a knight can make multiple moves in succession before arriving back at the same point.
The solution is to create a "board" containing a value for each possible co-ordinate that represents whether that has been visited or not. When you make a move to a valid square, if it is already marked as visited then you must return immediately. Otherwise, you can mark it as visited and continue checking.
Because you probably want to search all possible combinations of moves, then you should also mark the square as not visited before you return from your function.
You can declare your "board" like this:
std::vector<bool> visited(N * N);
And you can index like this:
visited[(y-1)*N + x-1] = true;
For ease, let's store this in the Solution class along with the answer, and make some adjustments:
class Solution
{
public:
int minStepToReachTarget(vector<int>& KnightPos, vector<int>& TargetPos, int N)
{
ans = -1;
visited.resize(N * N, false);
func(KnightPos[0], KnightPos[1], TargetPos[0], TargetPos[1], N, 0);
return ans;
}
private:
void func(int x, int y, int fr, int fc, int N, int cnt);
int ans;
vector<bool> visited;
};
Now, the function itself:
void func(int x, int y, int fr, int fc, int N, int cnt)
{
if(x > N || y > N || x < 1 || y < 1)
{
return;
}
// Target reached
if(x == fr && y == fc) {
ans = cnt;
return;
}
// Prune futile searches
cnt++;
if (ans >= 0 && ans <= cnt) return;
// Search
int vidx = (y - 1) * N + x - 1;
if (!visited[vidx])
{
visited[vidx] = true;
func(x + 2, y - 1, fr, fc, N, cnt);
func(x + 2, y + 1, fr, fc, N, cnt);
func(x - 1, y + 2, fr, fc, N, cnt);
func(x + 1, y + 2, fr, fc, N, cnt);
func(x - 2, y + 1, fr, fc, N, cnt);
func(x - 2, y - 1, fr, fc, N, cnt);
func(x - 1, y - 2, fr, fc, N, cnt);
func(x + 1, y - 2, fr, fc, N, cnt);
visited[vidx] = false;
}
}
Notice how the visited flags are being used here.
Also note a couple of extra important changes from above:
// Target reached
if(x == fr && y == fc) {
ans = cnt;
return;
}
// Prune futile searches
cnt++;
if (ans >= 0 && ans <= cnt) return;
The first bit simplifies your target-reached scenario. Quite simply, if you reach the target, you know that it's the best answer so far. How? Because of the second bit...
The second bit increments your step count and then checks if this can possibly produce a better answer than what we have already. If not, we stop searching. Such searching would be futile because even if you ultimately reach the target it will not be the shortest path. You should avoid such searches, because they can blow out your execution time by an insane amount.
发布评论
评论（1）
您的问题是堆栈溢出，因为每个递归级别都不知道已经检查了哪些位置。考虑一个简单的示例要说明：
您看到问题吗？上面的这两种情况将永远振荡，在您重复时增加堆栈中的更多内容，直到您用尽堆栈并终止操作系统为止。
现在，简单地记住最后一步是什么并排除在外是不够的，因为骑士可以在回到同一点之前连续迈出多个动作。
解决方案是创建一个“板”，其中包含每个可能的坐标值的值，该值表示是否已访问。当您搬到有效的广场时，如果已将其标记为已访问，则必须立即返回。否则，您可以将其标记为已访问并继续检查。
因为您可能想搜索所有可能的动作组合，因此您还应该在从功能返回之前将其标记为未访问的正方形。
您可以像这样声明您的“板”：
您可以这样索引：
为了轻松，让我们将其存储在解决方案类中以及答案中，然后进行一些调整：
现在，功能本身：
请注意
如何访问标志在这里使用。还要注意上面的几个额外的重要更改：
第一个位简化了您的目标方案。简而言之，如果您达到目标，那么您知道这是迄今为止最好的答案。如何？由于第二位...
第二位增加了您的步骤数，然后检查是否可以产生比我们已经有更好的答案。如果没有，我们停止搜索。这种搜索是徒劳的，因为即使您最终达到目标，也不是最短的路径。您应该避免进行此类搜索，因为它们可以通过疯狂的数量吹出您的执行时间。
Your issue is a stack overflow because each level of recursion has no knowledge of what positions have already been checked. Consider this simple example to illustrate:
Do you see the problem? These two cases above will oscillate forever, adding more to the stack as you recurse, until you run out of stack and the operating system terminates your process.
Now, it's not enough to simply remember what the last move is and exclude that, because a knight can make multiple moves in succession before arriving back at the same point.
The solution is to create a "board" containing a value for each possible co-ordinate that represents whether that has been visited or not. When you make a move to a valid square, if it is already marked as visited then you must return immediately. Otherwise, you can mark it as visited and continue checking.
Because you probably want to search all possible combinations of moves, then you should also mark the square as not visited before you return from your function.
You can declare your "board" like this:
And you can index like this:
For ease, let's store this in the Solution class along with the answer, and make some adjustments:
Now, the function itself:
Notice how the
visitedflags are being used here.Also note a couple of extra important changes from above:
The first bit simplifies your target-reached scenario. Quite simply, if you reach the target, you know that it's the best answer so far. How? Because of the second bit...
The second bit increments your step count and then checks if this can possibly produce a better answer than what we have already. If not, we stop searching. Such searching would be futile because even if you ultimately reach the target it will not be the shortest path. You should avoid such searches, because they can blow out your execution time by an insane amount.