我正在尝试使用C中的回溯来解决迷宫。要解决迷宫，请遵循以下规则：
- 你从S的位置开始，需要向E前进
- 你只能继续"。"路径
- 转换所有的"."转换为'#'，包括S和E
输入由一个m x n矩阵组成：输入示例：
11 11
+-+-+-+-+-+
S.|...|...|
+.+.+.+-+.+
|.|.|.....|
+.+-+-+-+.+
|...|.|...|
+.+.+.+.+-+
|.|...|.|.|
+.+-+.+.+.+
|...|.....E
+-+-+-+-+-+
预期解决方案：
+-+-+-+-+-+
##|...|...|
+#+.+.+-+.+
|#|.|.....|
+#+-+-+-+.+
|###|.|...|
+.+#+.+.+-+
|.|###|.|.|
+.+-+#+.+.+
|...|######
+-+-+-+-+-+
我真的很努力地想解决这个问题，但由于某种原因，一旦我到达迷宫中的一个点，我的程序就不会再回去了。它只是朝着它看到"的所有方向走
我的想法是从S的位置开始，在每个递归步骤中使用我们原来的位置。如果我所看到的位置是"，我会从我所站的位置向所有方向前进如果这不是我以前的立场。
我还认为，当我回到十字路口时，我会遇到问题。例如：
+-+-+-+-+-+
##|...|...|
+#+.+.+-+.+
|#|.|.....|
+#+-+-+-+.+
|0##|.|...|
+.+#+.+.+-+
|.|###|.|.|
+.+-+#+.+.+
|..1|######
+-+-+-+-+-+
想象一下我在0的位置。我从1反悔，把#改回"."。我怎么能发表声明说你有2#的可能性回去，但你应该停止？
我的代码：
#include <stdio.h>
#include <stdlib.h>
void *safeMalloc(int n) {
void *p = malloc(n);
if (p == NULL) {
printf("Error: malloc(%d) failed. Out of memory?n", n);
exit(EXIT_FAILURE);
}
return p;
}
char ** readMatrix(int m,int n,int* startI,int* startJ,int* endI,int* endJ){
char **arr = safeMalloc(m*sizeof(char *));
int row;
for (row=0; row < m; row++) {
arr[row] = safeMalloc(n*sizeof(char));
}
int i,j;
for(i=0;i<m;i++){
for(j=0;j<m;j++){
scanf(" %c",&arr[i][j]);
if(arr[i][j]=='S'){
*startI=i;
*startJ=j;
}
if(arr[i][j]=='E'){
*endI=i;
*endJ=j;
}
}
getchar();
}
return arr;
}
void printNumber(char **arr,int m,int n){
int i,j;
for(i=0;i<m;i++){
for(j=0;j<n;j++){
printf("%c", arr[i][j]);
}
printf("n");
}
}
void findPath(char** arr,int m,int n,int startI,int startJ,int endI,int endJ,int oldI,int oldJ){
int i=startI,j=startJ;
int stepsPossible=4;
//going up
if(i-1>=0){
if((arr[i-1][j]=='.') && ((i-1!=oldI) || (j!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i-1,j,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//going right
if(j+1<n){
if((arr[i][j+1]=='.') && ((i!= oldI) || (j+1!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j+1,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//going left
if(j-1>=0){
if((arr[i][j-1]=='.') && ((i!= oldI) || (j-1!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j-1,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//going down
if(i+1<m){
if((arr[i+1][j]=='.') && ((i+1!= oldI) || (j!=oldJ))){
arr[i][j]='#';
oldI=i;
oldJ=j;
findPath(arr,m,n,i+1,j,endI,endJ,oldI,oldJ);
}else{
stepsPossible--;
}
}
//if the next block is E then we can stop.
if((arr[i-1][j]=='E') || (arr[i][j+1]=='E') || (arr[i][j-1]=='E') || (arr[i+1][j]=='E')){
if(arr[i-1][j]=='E'){
arr[i-1][j]='#';
}
if(arr[i][j+1]=='E'){
arr[i][j+1]='#';
}
if(arr[i][j-1]=='E'){
arr[i][j-1]='#';
}
if(arr[i+1][j]=='E'){
arr[i+1][j]='#';
}
return;
}
if(stepsPossible==0){
if(arr[i-1][j]=='#'){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i-1,j,endI,endJ,oldI,oldJ);
}else{
return;
}
if(arr[i][j+1]=='#' ){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j+1,endI,endJ,oldI,oldJ);
}else{
return;
}
if(arr[i][j-1]=='#' ){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i,j-1,endI,endJ,oldI,oldJ);
}else{
return;
}
if(arr[i+1][j]=='#' ){
arr[i][j]='.';
oldI=i;
oldJ=j;
findPath(arr,m,n,i+1,j,endI,endJ,oldI,oldJ);
}else{
return;
}
}
}
int main()
{
int m,n;
scanf("%d %d",&m,&n);
int startI,startJ,endI,endJ;
char** arr;
arr=readMatrix(m,n,&startI,&startJ,&endI,&endJ);
findPath(arr,m,n,startI,startJ,endI,endJ,startI,startJ);
printNumber(arr,m,n);
return 0;
}
正确使用返回值，因为您可以利用它来简化逻辑。在findPath上为错误情况(需要回溯)和成功情况(到达终点)选择不同的返回值。
现在，您可以在该函数开始时无条件地设置#，并在回溯情况结束时无条件重置回.。
也不需要计算可能的方向，只需要检查某个呼叫是否返回成功。
同样，不需要一遍又一遍地写边界检查，如果你只是在函数开始时检查它们，你就可以毫无问题地传递无效坐标。
bool findPath(char** arr, size_t sx, size_t sy, int x, int y) {
if (x < 0 || x >= sx || y < 0 || y >= sy) return false;
if (arr[x][y] == 'E') {
are[x][y] = '#';
return true;
}
if (arr[x][y] != '.') return false;
arr[x][y] = '#';
bool success = findPath(arr, sx, sy, x-1, y) ||
findPath(arr, sx, sy, x+1, y) ||
findPath(arr, sx, sy, x, y-1) ||
findPath(arr, sx, sy, x, y+1);
if (!success) arr[x][y] = '.';
return success;
}
回溯算法的实现通常都遵循相同的模式：
- 试着简单地拒绝或接受当前的解决方案
- 修改当前解决方案
- 尝试变体
- 如果修改不成功，请进行清理
我建议使用BFS，因为
- BFS将找到最短的解决方案
- DFS对某些迷宫的处理非常非常差
以下是针对您的案例的BFS的简短描述：
- 在迷宫中找到"S"并将其添加到队列中
- 当队列不为空时，请检查队列中的get元素。将元素替换为"#"。若元素是E，那个么就完成了。检查元素的邻居(上、下、左、右)，如果它们是"."，则添加到队列中
- 若队列为空且未找到E，则从S到E并没有直接路径