回溯法解迷宫问题的两个解法

解法1：

/**//*
使用回溯法计算迷宫问题
*/
#include<stdio.h>
#include<stdlib.h>
structpos...{
introw;
intcol;
};
voidmain()...{
intmaze[5][5]=...{
0,1,0,1,0,
0,0,0,1,0,
0,1,0,1,0,
0,1,0,0,0,
0,0,1,1,0
};//1表示障碍，0表示可以通过
intdir=1;//标记方向：上1左2下3右4
inti=0;
intj=0;
structpos*stack=(structpos*)calloc(25,sizeof(structpos));
inttop=0;
while(true)...{
if(i==4&&j==4)...{//已经找到终点，打印结果
printf("Finish! Thepathis: ");
for(dir=0;dir<top;dir++)...{
printf("(");
printf("%d",stack[dir].row);
printf(",");
printf("%d",stack[dir].col);
printf(")");
}
printf("(4,4)");
break;
}
if(dir==1)...{
if(i>0&&*(*(maze+i-1)+j)==0//下一个位置不越界而且可以通过
&&!(stack[top-1].row==i-1&&stack[top-1].col==j))...{
//还需满足：这个将要走的位置不属于刚才走来的路！
stack[top].row=i;
stack[top].col=j;
top++;//进栈
i--;
dir=1;//重置方向标识
}else...{
dir++;
}
}
elseif(dir==2)...{
if(j>0&&*(*(maze+i)+j-1)==0
&&!(stack[top-1].row==i&&stack[top-1].col==j-1))...{
stack[top].row=i;
stack[top].col=j;
top++;
j--;
dir=1;
}else...{
dir++;
}
}
elseif(dir==3)...{
if(i<4&&*(*(maze+i+1)+j)==0
&&!(stack[top-1].row==i+1&&stack[top-1].col==j))...{
stack[top].row=i;
stack[top].col=j;
top++;
i++;
dir=2;
}else...{
dir++;
}
}
else...{
if(j<4&&*(*(maze+i)+j+1)==0
&&!(stack[top-1].row==i&&stack[top-1].col==j+1))...{
stack[top].row=i;
stack[top].col=j;
top++;
j++;
dir=1;
}else...{//已经没有别的路了，只有回头
*(*(maze+i)+j)=1;//在回头前标识当前路为不能通过
i=stack[top-1].row;
j=stack[top-1].col;
top--;//出栈
dir=1;//重置方向标识符
}
}
}
}

 

---

解法2：

 

/**//*
使用回溯法计算迷宫问题
*/
#include<stdio.h>
#include<stdlib.h>
structpos...{
introw;
intcol;
intdirection[5];//标记方向direction[1~4]上左下右
};
voidmain()...{
intmaze[5][5]=...{
0,1,0,1,0,
0,0,0,1,0,
0,1,0,1,0,
0,1,0,0,0,
0,0,1,1,0
};//1表示障碍，0表示可以通过
intdirection[5]=...{0};
intdir=1;//作为direction数组的下标
inti=0;
intj=0;
intcount=0;
structpos*stack=(structpos*)calloc(25,sizeof(structpos));//栈，存放路径
inttop=0;

//将栈内元素全部初始化
for(count=0;count<25;count++)...{
stack[count].col=0;
stack[count].row=0;
for(intt=0;t<=4;t++)
stack[count].direction[t]=0;
}

while(true)...{
if(i==1&&j==2)...{
intt=1;
};
if(i==4&&j==4)...{//已经找到终点，打印结果
printf("Finish! Thepathis: ");
for(count=0;count<top;count++)...{
printf("(");
printf("%d",stack[count].row);
printf(",");
printf("%d",stack[count].col);
printf(")");
}
printf("(4,4)");
break;
}
if(direction[1]==0
&&i>0
&&*(*(maze+i-1)+j)==0)...{//上方向的下一个位置不越界而且可以通过
stack[top].row=i;
stack[top].col=j;
direction[1]=1;
for(count=1;count<=4;count++)...{
stack[top].direction[count]=direction[count];
direction[count]=0;//使下一个位置方向状态初始化
}
direction[3]=1;//更新下一个位置：使朝向原位置的方向标识置1
top++;//进栈
direction[3]=1;
i--;
}
elseif(direction[2]==0
&&j>0
&&*(*(maze+i)+j-1)==0)...{//左方向的下一个位置不越界而且可以通过
stack[top].row=i;
stack[top].col=j;
direction[2]=1;
for(count=1;count<=4;count++)...{
stack[top].direction[count]=direction[count];
direction[count]=0;//使下一个位置方向状态初始化
}
direction[4]=1;//更新下一个位置：使朝向原位置的方向标识置1
top++;//进栈
j--;
}
elseif(direction[3]==0
&&i<4
&&*(*(maze+i+1)+j)==0)...{//下方向的下一个位置不越界而且可以通过
stack[top].row=i;
stack[top].col=j;
direction[3]=1;
for(count=1;count<=4;count++)...{
stack[top].direction[count]=direction[count];
direction[count]=0;//使下一个位置方向状态初始化
}
direction[1]=1;//更新下一个位置：使朝向原位置的方向标识置1
top++;//进栈
i++;
}
elseif(direction[4]==0
&&j<4
&&*(*(maze+i)+j+1)==0)...{//右方向的下一个位置不越界而且可以通过
stack[top].row=i;
stack[top].col=j;
direction[4]=1;
for(count=1;count<=4;count++)...{
stack[top].direction[count]=direction[count];
direction[count]=0;//使下一个位置方向状态初始化
}
direction[2]=1;//更新下一个位置：使朝向原位置的方向标识置1
top++;//进栈
j++;
}else...{//已经没有别的路了，只有回头
if(top==0)...{
printf("Nopath!");
break;
}
*(*(maze+i)+j)=1;//在回头前标识当前路为不能通过
top--;//出栈
i=stack[top].row;
j=stack[top].col;
for(count=1;count<=4;count++)
direction[count]=stack[top].direction[count];
}
//printf("(%d,%d)",i,j);
}//while
}