- /************************************
- *Copyright (c++) by xihua_university
- *All Rights Reserved
- *
- *Filename:寻找迷宫出口.cpp
- *Function:利用回溯法寻找迷宫出口
- *Environment:visual studio 2012
- *Auther:何晏波
- *Final:2013,10,7
- ************************************/
- #include<iostream>
- #include<list>
- using namespace std;
- struct Node
- {
- int x;
- int y;
- };
- Node CreateNode (int x,int y);//创建结点储存路径
- bool Jud_Boun (int x,int y,int horz,int vert);//边界检查
- list<Node> RecoderPath (int *metric,int horz,int vert,int x0,int y0,int x1,int y1);//记录迷宫路径
- void PrintPath (list<Node> List);//输出路径
- int main()
- {
- int *metric;/*[120] = {1,1,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,1,1,0,0,\\
- 0,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,1,1,1,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,1,1,0,\\
- 0,0,1,0,0,0,1,0,0,0,1,1};*///调试时的测试数据
- int horz/*(10)*/,vert/*(12)*/,x0 ,y0 ,x1 ,y1;
- printf ("请输入需找的迷宫矩阵的行数与列数:\\n");
- scanf ("%i%i",&horz,&vert);
- metric = new int[horz*vert];
- for (int i=0; i<horz; i++)
- {
- printf ("请输入矩阵第%d行的%d个标记值(1代表通道,0代表墙):\\n",i+1,vert);
- for (int j=0; j<vert; j++)
- scanf ("%d",&metric[i*vert+j]);
- }
- system ("cls");
- //入口坐标
- printf ("令起始点坐标为(1,1),请输入迷宫入口坐标:\\n");
- scanf ("%d%d",&x0,&y0);//输入入口坐标
- while (metric[(x0-1)*vert+y0-1]!=1)//检查入口坐标合法性
- {
- printf ("输入的坐标非法!请重新输入:\\n");
- scanf ("%d%d",&x0,&y0);
- }
- //出口坐标
- printf ("请输入迷宫出口坐标:\\n");
- scanf ("%d%d",&x1,&y1);//输入出口坐标
- while (metric[(x1-1)*vert+y1-1]!=1)//检查出口坐标合法性
- {
- printf ("输入的坐标非法!请重新输入:\\n");
- scanf ("%d%d",&x1,&y1);
- }
- list<Node>List (RecoderPath (metric,horz,vert,x0-1,y0-1,x1-1,y1-1));//定义路径链表
- PrintPath (List);
- system("pause");
- return 0;
- }
- /***创建结点***/
- Node CreateNode (int x,int y)
- {
- Node node;
- node.x = x;
- node.y = y;
- return node;
- }
- /***边界检查***/
- bool Jud_Boun (int x0,int y0,int horz,int vert)
- {
- if (x0>-1 && x0<horz && y0>-1 && y0<vert)
- return true;
- return false;
- }
- /***路径记录***/
- list<Node> RecoderPath (int *metric,int horz,int vert,int x0,int y0,int x1,int y1)
- {
- int prior;
- list<Node> List;
- Node node;
- if (x1>=x0 && y1>=y0)//根据迷宫起始点与终点的横纵坐标大小确定访问方向的优先顺序
- prior = 1;
- if (x1>=x0 && y1<y0)
- prior = 2;
- if (x1<x0 && y1<=y0)
- prior = 3;
- if (x1<x0 && y1>y0)
- prior = 4;
- List.push_back (CreateNode (x0,y0));
- metric[x0*vert+y0] = 0;//标记已经走过
- switch (prior)
- {
- case 1://南和东优先
- while (!(x0==x1&&y0==y1) && !List.empty())//循环结束的条件是找到出口或者没有找到出口
- {
- if(Jud_Boun (x0+1,y0,horz,vert) && metric[(x0+1)*vert+y0] == 1)
- {
- List.push_back (CreateNode (x0+1,y0));
- metric[(x0+1)*vert+y0] = 0;//标记已经向南走过的点
- x0 += 1;
- }
- else if (Jud_Boun (x0,y0+1,horz,vert) && metric[(x0)*vert+y0+1]==1)
- {
- List.push_back (CreateNode (x0,y0+1));
- metric[(x0)*vert+y0+1] = 0;//标记已经向东走过的点
- y0 += 1;
- }
- else if (Jud_Boun (x0-1,y0,horz,vert) && metric[(x0-1)*vert+y0]==1)
- {
- List.push_back (CreateNode (x0-1,y0));
- metric[(x0-1)*vert+y0] = 0;//标记已经向北走过的点
- x0 -= 1;
- }
- else if(Jud_Boun (x0,y0-1,horz,vert) && metric[(x0)*vert+y0-1]==1)
- {
- List.push_back (CreateNode (x0,y0-1));
- metric[(x0)*vert+y0-1] = 0;//标记已经向西走过的点
- y0 -= 1;
- }
- else
- {
- List.pop_back();//遇到墙壁从链表末尾退栈
- x0 = List.back().x;//退栈后坐标应该回到上一个初始状态
- y0 = List.back().y;
- }
- }
- break;
- case 2://西和南优先
- while (!(x0==x1&&y0==y1) && !List.empty())//循环结束的条件是找到出口或者没有找到出口
- {
- if(Jud_Boun (x0,y0-1,horz,vert) && metric[(x0)*vert+y0-1]==1)
- {
- List.push_back (CreateNode (x0,y0-1));
- metric[(x0)*vert+y0-1] = 0;//标记已经向西走过的点
- y0 -= 1;
- }
- else if (Jud_Boun (x0-1,y0,horz,vert) && metric[(x0-1)*vert+y0]==1)
- {
- List.push_back (CreateNode (x0-1,y0));
- metric[(x0-1)*vert+y0] = 0;//标记已经向北走过的点
- x0 -= 1;
- }
- else if(Jud_Boun (x0+1,y0,horz,vert) && metric[(x0+1)*vert+y0] == 1)
- {
- List.push_back (CreateNode (x0+1,y0));
- metric[(x0+1)*vert+y0] = 0;//标记已经向南走过的点
- x0 += 1;
- }
- else if (Jud_Boun (x0,y0+1,horz,vert) && metric[(x0)*vert+y0+1]==1)
- {
- List.push_back (CreateNode (x0,y0+1));
- metric[(x0)*vert+y0+1] = 0;//标记已经向东走过的点
- y0 += 1;
- }
- else
- {
- List.pop_back();//遇到墙壁从链表末尾退栈
- x0 = List.back().x;//退栈后坐标应该回到上一个初始状态
- y0 = List.back().y;
- }
- }
- break;
- case 3://北西优先
- while (!(x0==x1&&y0==y1) && !List.empty())//循环结束的条件是找到出口或者没有找到出口
- {
- if (Jud_Boun (x0-1,y0,horz,vert) && metric[(x0-1)*vert+y0]==1)
- {
- List.push_back (CreateNode (x0-1,y0));
- metric[(x0-1)*vert+y0] = 0;//标记已经向北走过的点
- x0 -= 1;
- }
- else if(Jud_Boun (x0,y0-1,horz,vert) && metric[(x0)*vert+y0-1]==1)
- {
- List.push_back (CreateNode (x0,y0-1));
- metric[(x0)*vert+y0-1] = 0;//标记已经向西走过的点
- y0 -= 1;
- }
- else if(Jud_Boun (x0+1,y0,horz,vert) && metric[(x0+1)*vert+y0] == 1)
- {
- List.push_back (CreateNode (x0+1,y0));
- metric[(x0+1)*vert+y0] = 0;//标记已经向南走过的点
- x0 += 1;
- }
- else if (Jud_Boun (x0,y0+1,horz,vert) && metric[(x0)*vert+y0+1]==1)
- {
- List.push_back (CreateNode (x0,y0+1));
- metric[(x0)*vert+y0+1] = 0;//标记已经向东走过的点
- y0 += 1;
- }
- else
- {
- List.pop_back();//遇到墙壁从链表末尾退栈
- x0 = List.back().x;//退栈后坐标应该回到上一个初始状态
- y0 = List.back().y;
- }
- }
- break;
- case 4://东北优先
- while (!(x0==x1&&y0==y1) && !List.empty())//循环结束的条件是找到出口或者没有找到出口
- {
- if (Jud_Boun (x0,y0+1,horz,vert) && metric[(x0)*vert+y0+1]==1)
- {
- List.push_back (CreateNode (x0,y0+1));
- metric[(x0)*vert+y0+1] = 0;//标记已经向东走过的点
- y0 += 1;
- }
- else if (Jud_Boun (x0-1,y0,horz,vert) && metric[(x0-1)*vert+y0]==1)
- {
- List.push_back (CreateNode (x0-1,y0));
- metric[(x0-1)*vert+y0] = 0;//标记已经向北走过的点
- x0 -= 1;
- }
- else if(Jud_Boun (x0,y0-1,horz,vert) && metric[(x0)*vert+y0-1]==1)
- {
- List.push_back (CreateNode (x0,y0-1));
- metric[(x0)*vert+y0-1] = 0;//标记已经向西走过的点
- y0 -= 1;
- }
- else if(Jud_Boun (x0+1,y0,horz,vert) && metric[(x0+1)*vert+y0] == 1)
- {
- List.push_back (CreateNode (x0+1,y0));
- metric[(x0+1)*vert+y0] = 0;//标记已经向南走过的点
- x0 += 1;
- }
- else
- {
- List.pop_back();//遇到墙壁从链表末尾退栈
- x0 = List.back().x;//退栈后坐标应该回到上一个初始状态
- y0 = List.back().y;
- }
- }
- break;
- default:
- break;
- }
- return List;
- }
- /***输出路径***/
- void PrintPath (list<Node> List)
- {
- printf("迷宫路径如下:\\n");
- printf("(%d,%d)",List.front().x+1,List.front().y+1);
- List.pop_front();
- while (!List.empty())
- {
- printf("->(%d,%d)",List.front().x+1,List.front().y+1);
- List.pop_front();
- }
- printf("\\n");
- }
- //该片段来自于http://www.codesnippet.cn/detail/160520149612.html
来源: http://www.codesnippet.cn/detail/160520149612.html