📄 迷宫问题.txt
字号:
迷宫问题
class TMaze //迷宫类
{
public:
TMaze(){} //构造函数
TMaze(char* fname); //构造函数，初始化
void BFS(); //成员函数，广度优先搜索
void Back(); //成员函数，回溯法
private:
int *p,*q; //数据成员，迷宫构造、访问标志
int row,col,last; //数据成员，当前坐标，父结点指针
static int rows,cols,number,exitrow,exitcol,mark; //数据成员，迷宫入口、出口坐标，路径足迹
static int d[]; //数据成员，位移坐标增量
void Print(); //成员函数，打印迷宫
void Print(TList<TMaze> L); //成员函数，打印BFS路径
bool Extend(int); //成员函数，判断给定方向可否通过
};
//静态数据成员，可供全体对象共享
int TMaze::rows,TMaze::cols,TMaze::number;
int TMaze::exitrow,TMaze::exitcol,TMaze::mark;
int TMaze::d[]={0,1,0,-1,0};
//构造函数，从文件读入迷宫数据，初始化迷宫
TMaze::TMaze(char* fname)
{
ifstream fin;
fin.open(fname,ios::in | ios::nocreate);
if(!fin)
{
cout<<"不能打开数据文件!"<<endl;
return;
}
fin>>rows>>cols; //读入迷宫行列数
fin>>row>>col>>exitrow>>exitcol; //读入迷宫入口出口坐标
number=rows*cols; //存储单元总数
p=new int[number]; //申请迷宫数据存储单元
q=new int[number]; //申请迷宫各点访问标志存储单元
for(int i=0;i<number;i++) //读入迷宫数据
{
fin>>p[i];
q[i]=p[i]; //设置访问标志，0——通道，未访问，1——墙
}
fin.close(); //关闭文件
last=0; //入口的父结点
}
//成员函数，打印迷宫结构
void TMaze::Print()
{
for(int i=0;i<number;i++)
{
cout<<setw(3)<<p[i];
if((i+1)%cols==0)
cout<<endl;
}
cout<<endl;
}
////成员函数，BFS找到的路径要从出口返回才能确定
void TMaze::Print(TList<TMaze> L)
{
if(last==0) //返回入口
return; //结束
else //否则
{
TMaze T=L.GetItem(last); //找到结点的父结点
T.Print(L); //递归
p[T.row*cols+T.col]=++mark; //设置足迹
}
}
//成员函数，判断给定方向是否可通过，不能则返回0，能则返回行位置
bool TMaze::Extend(int i)
{
int newrow=row+d[i]; //方向i前进一步的新坐标
int newcol=col+d[i+1];
if(p[newrow*cols+newcol]==1 || q[newrow*cols+newcol]==1)//若该点是墙或已经经过
return 0; //不能向该方向前进
row=newrow; //否则可前进，修改当前位置坐标
col=newcol;
q[newrow*cols+newcol]=1; //设置已访问标志
return 1; //返回可通过信息
}
//成员函数，用广度优先搜索搜索路径
void TMaze::BFS()
{
TMaze T=*this; //中间对象变量
TList<TMaze> L; //设置队列
L.InList(T); //起始结点进入队列
p[row*cols+col]=mark=1; //起点足迹
q[row*cols+col]=1; //起点已被访问
int head=0,tail=0; //队列头和尾指针
while(head<=tail) //队列不空时循环
{
for(int i=0;i<4;i++) //顺序从东（0）、南（1）、西（2）、北（3）四个方向试探寻找通路
{
T=L.GetItem(head); //从队列中取出头指针所指结点
if(T.Extend(i)) //如果在方向i可前进一步
{
T.last=head; //记录其父结点
L.InList(T); //将新结点加入队列
tail++; //移动尾指针
}
if(T.row==exitrow && T.col==exitcol) //如果该结点是出口
{
T.Print(L); //递归找出路经
p[T.row*cols+T.col]=++mark; //设置出口足迹
T.Print(); //输出包含路径的迷宫
return; //结束
}
} //一个结点的各个方向都已试探过
head++; //将队列头指针向后移，只想未检查的结点
}
cout<<"未找到通路。"<<endl;
}
//成员函数，回溯法搜索路径
void TMaze::Back()
{
TMaze T=*this; //中间对象变量
TList<TMaze> L; //设置堆栈
L.Push(T); //起始结点进栈
p[row*cols+col]=mark=1; //入口足迹
q[row*cols+col]=1; //入口已被访问
while(L.Getlen()>0) //当堆栈不空时循环
{
for(int i=0;i<4;i++) //顺序从东（0）、南（1）、西（2）、北（3）四个方向试探寻找通路
{
T=L.GetTop(); //取出栈顶元素
if(T.row==exitrow && T.col==exitcol) //若该结点是出口
{
T.Print(); //输出迷宫
return; //结束
}
if(T.Extend(i)) //否则，如果在方向i可前进一步
{
p[T.row*cols+T.col]=++mark; //设置该点足迹
q[T.row*cols+T.col]=1; //设置该点已被访问
L.Push(T); //将新结点入栈
break; //不再检查其他方向
}
}
if(i==4) //若结点各个方向都不能前进
{
p[T.row*cols+T.col]=0; //恢复原来状态
mark--; //恢复足迹
L.Pop(); //将该结点出栈,退回前一点
}
}
cout<<"找不到通路。"<<endl;
}
//简单的线性链表，既可作为队列，也可作为堆栈使用
//TList.h
template<class Type> class TList;
template<class Type> class TNode
{
friend class TList<Type>;
public:
TNode(){Next=0;Type();}
private:
TNode<Type>* Next;
Type Data;
};
template<class Type> class TList
{
public:
TList(){Last=0;Length=0;}
int Getlen()const{return Length;}
void InList(const Type& T);
void Push(const Type& T);
Type Pop();
Type GetTop()const{return Last->Next->Data;}
Type GetItem(int)const;
private:
TNode<Type>* Last;
int Length;
};
template<class Type> void TList<Type>::InList(const Type& T)
{
TNode<Type> *p=new TNode<Type>;
p->Data=T;
if(Last)
{
p->Next=Last->Next;
Last=Last->Next=p;
}
else
Last->Next=Last=p;
Length++;
}
template<class Type> void TList<Type>::Push(const Type& T)
{
TNode<Type>* p=new TNode<Type>;
p->Data=T;
if(Last)
{
p->Next=Last->Next;
Last->Next=p;
}
else
Last->Next=Last=p;
Length++;
}
template<class Type> Type TList<Type>::Pop()
{
TNode<Type>* p=Last->Next;
Type dat=p->Data;
Last->Next=Last->Next->Next;
Length--;
delete p;
return dat;
}
template<class Type> Type TList<Type>::GetItem(int k)const
{
TNode<Type> *p=Last->Next;
while(k-->0)
p=p->Next;
return p->Data;
}
#include<iostream.h>
#include<iomanip.h>
#include<fstream.h>
#include<TList.h>
#include"TMaze.h"
//测试函数
int main()
{
char f[]=".\\maze.txt"; //数据文件
TMaze T(f); //初始化
T.BFS(); //广度优先搜索法
//T.Back(); //回溯法
return 0;
}
//迷宫数据文件
//maze.txt
23 22 1 0 21 21 //迷宫行列数、入口、出口坐标
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1
1 0 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 0 1
1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1
1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1
1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1
1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1
1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1
1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1
1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1
1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1
1 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1
1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1
1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
//BFS执行结果
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
1 3 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 4 5 6 7 8 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 9 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1
1 14 13 12 11 10 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1
1 15 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 0 1
1 16 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1
1 17 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1
1 18 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1
1 19 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1
1 20 21 22 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1
1 1 1 23 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1
1 0 0 24 25 26 27 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1
1 1 1 1 1 1 28 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1
1 34 33 32 31 30 29 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1
1 35 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1
1 36 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1
1 37 1 1 1 1 1 1 50 51 52 1 58 59 60 61 0 0 0 0 1 1
1 38 0 0 0 0 0 1 49 1 53 1 57 1 1 62 1 1 1 1 1 1
1 39 1 1 1 1 1 1 48 1 54 55 56 0 1 63 1 1 1 1 1 1
1 40 41 42 43 44 45 46 47 1 0 1 1 0 1 64 65 66 67 68 69 71
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
//回溯法执行结果
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 0 0 0 1 11 12 13 1 0 0 0 0 0 0 0 0 0 0 0 1
1 3 1 1 1 1 10 1 14 1 1 1 1 1 1 1 1 1 1 1 0 1
1 4 5 6 7 8 9 1 15 16 17 1 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 0 1 1 1 1 18 1 0 1 1 1 1 1 1 1 0 1
1 0 0 0 0 0 1 0 0 0 19 1 0 1 29 30 31 32 33 34 35 1
1 0 1 1 1 0 1 0 1 1 20 21 22 1 28 1 1 1 1 1 36 1
1 0 1 0 1 1 1 0 1 0 1 1 23 1 27 1 49 48 47 1 37 1
1 0 1 0 0 0 1 0 1 0 0 0 24 25 26 1 50 1 46 1 38 1
1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 1 51 1 45 1 39 1
1 0&
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -