使用递归的迷宫最短路径

本文介绍了使用递归的迷宫最短路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

首先，我想指出的是，我之前曾发布过相同的问题，但没有找到正确的答案，因此对不起重复这个问题.

First of all I want to note that I posted this same question before and did not found a right answer, so sorry for repeating question.

请注意，我必须在此处使用递归.我知道通常使用BFS可以找到最短路径，这不是递归的，但是我需要知道如何以递归的方式实现.

Note that I am required to use recursion here. I am aware that shortest path is usually found using BFS, which is not recursive, but I need to know how can this be done recursively.

我正在做胭脂游戏，我的一个怪物的行为是这样的.在迷宫中，如果怪物可以15步或更少的步数到达玩家，它就会使最佳移动成为可能.为了实现这一点，我编写了一个小程序，基本上模仿了游戏中将要发生的事情.我的程序以一种能够检查x的移动量是否会将他带到目的地的方式工作.我不确定的唯一部分是如何获得第一步，因此我可以将该信息传递给我的怪物移动功能.这是我到目前为止编写的程序.

I am working on a rouge game and one of my monsters behaves like this. In a maze, if monster can reach the player in 15 or less steps, it makes the most optimal move possible. In order to implement this, I wrote a small program mimicking basically what is going to happen in my game. My program works in a way that it is able to check if x amount of moves will get him to destination. The only part I am not sure is how to get the first step, so I can pass that info to my monster move function. Here is the program that I wrote so far.

我的一位同学建议用不同的值填充空白处，并以这种方式找到路径，但我不明白他的意思.有人可以向我解释如何做到这一点吗?

One of my fellow students suggests to fill the empty space with different values and find the path that way, but I could not understand what he meant. Can someone explain to me how this can be done?

#include <iostream> using namespace std; bool pathExists(char maze[][10], int sr, int sc, int er, int ec, int distance) { if (maze[sr][sc] != '.') return false; if (sr == er && sc == ec) return true; if(distance == 15) { cout<<"Cant make it in 15 steps"<<endl; return false; } maze[sr][sc] = '@'; // anything non-'.' will do if (pathExists(maze, sr-1, sc, er, ec, distance+1)) return true; if (pathExists(maze, sr+1, sc, er, ec,distance+1)) return true; if (pathExists(maze, sr, sc-1, er, ec, distance+1)) return true; if (pathExists(maze, sr, sc+1, er, ec, distance+1)) return true; return false; } int main() { char maze[10][10] = { { 'X','X','X','X','X','X','X','X','X','X'}, { 'X','.','.','.','.','.','.','.','.','X'}, { 'X','.','X','X','X','X','.','X','X','X'}, { 'X','.','.','X','.','X','.','.','.','X'}, { 'X','.','.','X','.','.','.','X','.','X'}, { 'X','.','X','X','.','X','X','X','.','X'}, { 'X','.','X','.','.','.','.','X','X','X'}, { 'X','.','.','X','X','.','X','X','.','X'}, { 'X','.','.','x','.','.','.','.','.','X'}, { 'X','X','X','X','X','X','X','X','X','X'} }; if (pathExists(maze, 8,8, 1,1,0)) cout << "Solvable!" << endl; else cout << "Out of luck!" << endl; }

推荐答案

您的算法效果很好.唯一缺少的是如果测试的路径不成功，则要在pathExist()中还原'.':

Your algorithm works well. The only thing missing is to restore the '.' in pathExist() if the tested path is not successful :

... if(pathExists(maze, sr, sc + 1, er, ec, distance + 1)) return true; maze[sr][sc] = '.'; //<=========== add this to restore the maze state return false; }

如果没有此行，则尝试找到正确路径的失败尝试将用'@'填充数组，以便后续探索不会找到任何实际的".不再.

Without this line, your failed attempts to find the right path will fill the array with '@' so that subsequent exploration will not find any praticable '.' anymore.

顺便说一句，由于位置[8][3]上的'x'，您在问题中发布的迷宫在少于15次的尝试中无法解决.

By the way, the maze that you've posted in your question is not solvable in less than 15 attempts, because of the 'x' in position [8][3].

其他评论:

您还问过它是如何工作的.实际上，没有"@"技巧的递归算法没有内存.因此，在递归调用中，它不记得它来自何处，这将导致无限递归，具体取决于以下模式: 将当前位置临时更改为"@"的事实就像您要标记当前正在探索的路径的不同单元格一样:

You've also asked how this work. In fact, your recursive algorithm without the trick of the '@' has no memory. So in the recursive call, it doesn't remember were it came from, which will result in infinite recursion accrding to the following pattern: The fact of changing the current position temporarily to '@' is as if you'd mark the different cells of the path currently being explored:

请注意，如果最后打印出网格，则会看到找到的完整路径(删除了有问题的"x"):

Note that if you print out the grid at the end, you'll see the full path that was found (with the problematic 'x' removed):