回溯法解迷宫问题的两个解法
程序员文章站
2022-05-06 12:11:29
...
解法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;//重置方向标识符
}
}
}
}
使用回溯法计算迷宫问题
*/
#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
}
使用回溯法计算迷宫问题
*/
#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
}
上一篇: 软件设计--用例图
下一篇: 小心程序中的时间(时间调整/闰秒)
推荐阅读