Jiankai
返回

数据结构迷宫问题C++链栈实现

更新于:
算法与数据结构

更新：使用回溯法求解迷宫问题（获取最优路径）

原文章使用方法过于愚蠢，请忽略

说明 N 代表迷宫，A代表方位暂存器，V代表对应的N点是否被访问，AS代表方位存储器，Step代表下一步的操作。

#include<iostream>
using namespace std;
int N[10001][10001];
int A[10001][2];
int V[10001][10001];
int AS[10001][2];

int Step[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int n;
int MinStep = 100000;

void Search(int s){
	for(int i=0;i<4;i++){
		int x = A[s-1][0]+Step[i][0];
		int y = A[s-1][1]+Step[i][1];
		if(x>=1 && x<=n && y>=1 && y<=n && V[x][y] != 1 && N[x][y] != 1 && s<MinStep){
			V[x][y] = 1;
			A[s][0] = x;
			A[s][1] = y;
			if(A[s][0] == n && A[s][1] == n){
				if(s<MinStep){
					for(int j=1;j<=s;j++){
						AS[j][0] = A[j][0];
						AS[j][1] = A[j][1];
					}
					MinStep = s;
				}
			}else{
				Search(s+1);
			}
			V[x][y] = 0;
		}
	}
}
int main(){
	A[1][0] = A[1][1] = 1;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>N[i][j];
		}
	}
	Search(2);
	cout<<MinStep<<endl;
	for(int j=1;j<=MinStep;j++){
		cout<<AS[j][0]<<" "<<AS[j][1]<<endl; 
	}
	return 0;
}

原文章：

刚刚学完栈时，拿到这个题目的瞬间 感觉自己的栈知识都白学了。不是因为不会使用栈，而是因为自己一点解题思路都没有，后来通过自己的一些推敲和查看一些资料，终于弄明白了如何求解。
接下来通过写出一些关键点，大家可以加以参考）

解题思路

  • 首先要建立一个用于存放方位信息的结构体类型Point(包括三个数据成员：行标row,列标col,下一步要走的方向way);

  • 然后建立一个头节点指针类型LStack（包括方位信息Point类型的p 和 后继地址next），而这个链栈就是我们将要存放的路径信息。

  • 分别写出入栈In和出栈Out的函数

  • 遍历函数Display，注意因为栈的特性是先进后出，所有我们在显示的时候需要把链栈逆序输出

  • 接下来就是最重要的Found，该函数要做的就是寻找路径

    1. 首先定义一个二维数组，这个数组map就是作为地图的存在，其中1代表不能走，0可走。
    2. 我们把数组的四边都定义为1，其余内部码入整个地图的数据；
    3. 定义Point类型的起点Home和End以及当前格子temp；
    4. 进入循环（当temp到达End时终止循环）当temp每到达新的一个格子时，都要对（除了temp原来的格子相对于当前temp的方向（比如原来temp在当前temp的上方，则在本次判定中不再对当前temp的上方进行判断））的所有方向进行判断：如果为0且路径链栈top的数据元素不含当前temp的值时则成功入栈，否则判断下一个方向。如果上下左右都不满足以上条件时则说明该格子是断头路需要退栈返回到上一个格子中并将该格子标记为-1。
    5. 如此循环下来，如果起点被标记成了断头路则说明该迷宫无正确路径，返回false。如果temp为终点End值则说明成功找到路径并以保存再链栈top中，返回true.

至此，我们的工作已经基本完成了，只需要再主函数main中建立一个链表再调用相关函数即可。

代码实现

#include<iostream>  
#include<cstdlib>  
using namespace std;  
typedef struct {    //用于封装方位及方向   
    int col,row,way;                 //0,1,2,3分别代表上、下、左、右   
}Point;  
  
typedef struct T{  //路径链表节点   
    Point P;  
    struct T *next;  
}LStack;  
  
void In(LStack *top,Point temp){  //入栈   
    LStack *s=(LStack *)malloc(sizeof(LStack));  
    s->P=temp;  
    s->next=top->next;  
    top->next=s;  
}   
  
bool Out(LStack *top){       //出栈   
    if(top->next==NULL)return false;  
    else {  
        LStack *p=top->next;  
        top->next=p->next;  
        free(p);  
        return true;  
    }  
}  
bool Query(LStack *top,Point temp){ //查询栈中是否存在temp值   
    LStack *p=top->next;  
    while(p!=NULL){  
        if(p->P.row==temp.row && p->P.col==temp.col)return true;  
        p=p->next;  
    }  
    return false;  
}  
  
bool Found(LStack *top){  
    int height,width;  
    height=9;width=8;  
    Point Home,End,temp;  
    Home.row=1;Home.col=1;  
    End.row=9;End.col=8;  
    int map[][10]={  
    {1,1,1,1,1,1,1,1,1,1},  
    {1,0,0,1,0,0,0,1,0,1},  
    {1,0,0,1,0,0,0,1,0,1},  
    {1,0,0,0,0,1,1,0,1,1},  
    {1,0,1,1,1,0,0,1,0,1},  
    {1,0,0,0,1,0,0,0,0,1},  
    {1,0,1,0,0,0,1,0,1,1},  
    {1,0,1,1,1,1,0,0,1,1},  
    {1,1,1,0,0,0,1,0,1,1},  
    {1,1,1,0,0,0,0,0,0,1},  
    {1,1,1,1,1,1,1,1,1,1}  
    };  
    temp.col=Home.col;temp.row=Home.row;  
    do{  
        for(temp.way=0;temp.way<=3;temp.way++){  
            if(top->next!=NULL && ((top->next->P.way+2)%4==temp.way))continue;  //解决上下，左右重复死循环问题   
            if(temp.way==0){  
                if(map[--temp.row][temp.col]==0 && !Query(top,temp)){  
                    temp.row++;  
                    In(top,temp);  
                    temp.row--;  
                    break;  
                }  
                else{  
                    temp.row++;  
                    continue;  
                }  
            }  
            if(temp.way==1){  
                if(map[temp.row][++temp.col]==0 && !Query(top,temp)){  
                    temp.col--;  
                    In(top,temp);  
                    temp.col++;  
                    break;  
                }  
                else{  
                    temp.col--;  
                    continue;  
                }  
            }  
            if(temp.way==2){  
                if(map[++temp.row][temp.col]==0 && !Query(top,temp)){  
                    temp.row--;  
                    In(top,temp);  
                    temp.row++;  
                    break;  
                }  
                else{  
                    temp.row--;  
                    continue;  
                }  
            }  
            if(temp.way==3){  
                if(map[temp.row][--temp.col]==0 && !Query(top,temp)){  
                    temp.col++;  
                    In(top,temp);  
                    temp.col--;  
                    break;  
                }  
                else{  
                    temp.col++;  
                    continue;  
                }  
            }  
        }  
        if(temp.way>3){     //无路可走时将点标-1并退栈   
            if(temp.row==Home.row && temp.col==Home.col)return false;  
            map[temp.row][temp.col]=-1;  
            Out(top);  
            temp=top->next->P;  
        }   
    }while(!(temp.row==End.row && temp.col==End.col));  
    temp.way=4;          
    In(top,temp);           //到达出口，入栈出口信息   
    return true;   
}  
void Display(LStack *top){     //通过头插二次入栈实现逆序链表.   
    LStack *s,*p=top->next;  
    top->next=NULL;  
    while(p!=NULL){  
        if(p->next!=NULL && p->P.col==p->next->P.col && p->P.row==p->next->P.row)p=p->next; //解决原路径中会存在一些判断退回时产生的数据冗余问题。   
        s=p;  
        p=p->next;  
        s->next=top->next;  
        top->next=s;  
    }   
    while(s!=NULL){  
        cout<<s->P.row<<" "<<s->P.col<<" "<<s->P.way<<endl;   
        s=s->next;  
    }  
}  
int main(){  
    LStack *top=(LStack *)malloc(sizeof(LStack));  
    top->next=NULL;  
    if(Found(top)){  
        cout<<"存在正确路径，如下(row,col,方向（0上,1右,2下,3左，4出口）)："<<endl;  
        Display(top);  
    }  
    else cout<<"无法到达出口"<<endl;   
    return 0;  
}

目前存在的问题

在图中其实已经看的出来，在寻找路径时有可能会绕远路，虽然能够到达终点，但是这不符合我们寻找最优路径的期望

上一篇
第一篇博客纪念
下一篇
哈夫曼树