本文目录
- 迷宫算法 上下左右 优先级问题
- C语言编程 迷宫问题(队列)
- 关于计算机C++编程的迷宫问题的解题思路
- c语言的迷宫问题
- 递归求解:右手扶墙法寻找迷宫出路
- 用递归算法找出迷宫中所有可行的路径
- 求一个求从迷宫的一点到另一点的最短路径的递归算法
- 设计一迷宫,并对其求解,输出从入口到出口的路径
- 数据结构算法 用C++ 迷宫最短路径
- 求解c语言一递归迷宫问题
迷宫算法 上下左右 优先级问题
迷宫一般采用递归算法,而且出口位置在算法开始时候是不知道的吧。而且迷宫的棚悉出口也不会固定到哪一个链指乎方向。如果采用枚举方法一般是按顺时针或者逆时逗棚针找,这样才可以用循环来做,如果采用优先,只能将每个方向定位,设一个常量,那样的话每次递归都要判断一下,非常麻烦,估计还比不用优先还慢一些。
C语言编程 迷宫问题(队列)
c#界面绘制的时隐猛候,底层重绘每次会清除画布背散氏景,然后再全部重新绘制,这才是导致闪烁最主要的原因。于是重载消冲携散息发送函数操作,禁掉这条消息。代码如下: protected override void WndProc(ref Message m) { if (m.Msg == 0x0014) // 禁掉清除背景消息 return; base.WndProc(ref m); }
关于计算机C++编程的迷宫问题的解题思路
/*走通用迷宫问题的思路是:从给定的任意一个起点开始,向各个方向都有走动的可能,按照一定的顺序进行。判断如果该方向上能走,(能走要是:不是以前走过的地方,不是墙壁,不是地图之外)就走这一步,然后记录下这一步。如果不能走,就换下一个方向,如果能走就继续下一步。各个方向都不能走,说明到了死路,这时候就返回上一步去走下一个方向。如此继续。每走动一步都要检测是不是到达目标了,如果到达就输出结果。如果不能走到目标,返回到最除起点也不能走了,说明无解。我的示意程序如下:*//*地图路径求解程序,用VC++编写的,*/#include《stdio.h》#include《stdlib.h》#defineROW9/*定义行数*/#defineCOL13/*定义列数*/typedefstructRowAndColPath{intr;intc;}RowAndColPath;/*定义结构体实现走步过程的记录*/intMove={{0,1},{1,0},{-1,0},{0,-1}};/*4个方向*/RowAndColPathpath;/*走动过程的记录*/boolResultFlag=false;/*找到解的标志*/boolGettingPath(intstep,intCurrentRow,intCurrentCol,intResultRow,intResultCol,intMapWay);/*递归求解方法*/voidmain(){intMapWay={{1,1,1,1,1,1,1,1,0,1,1,1,1},{0,0,0,1,1,0,0,0,0,1,1,1,1},{1,1,0,1,1,1,1,1,0,0,1,1,1},{1,1,0,0,0,0,1,1,1,0,1,1,1},{1,1,0,1,1,0,0,0,0,0,0,0,1},{1,1,0,0,1,1,1,1,1,1,1,0,1},{1,1,1,0,0,0,0,0,0,1,1,0,1},{1,1,1,0,1,1,1,1,0,0,0,0,1},{1,1,1,0,0,0,1,1,1,1,1,1,1}};/*定义地图*/intCurrentRow=1,CurrentCol=0,ResultRow=0,ResultCol=8;/*定义初始和结束位置*/path.r=CurrentRow;path.c=CurrentCol;/*初始位置进入历史的第一步*/if(GettingPath(1,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay))/*如果走动成功*/printf("恭喜!查找成功!\n");elseprintf("抱歉,查找失败!\n");}boolGettingPath(intstep,intCurrentRow,intCurrentCol,intResultRow,intResultCol,intMapWay){inti,j;for(i=0;i《4;i++)/*依次对4个方向搜索*/{if(ResultFlag)returntrue;CurrentRow+=Move;CurrentCol+=Move;/*先按该方向前进一步*/if((CurrentRow》=0)&&(CurrentRow《ROW)&&(CurrentCol》=0)&&(CurrentRow《COL))/*如果还在地图内部*/{if(MapWay==0)/*下一步可以走*/{for(j=0;j《step;j++)/*判断是不是重复了以前走过的路*/{if((path.c==CurrentCol))break;}if(j==step)/*如果没有走过这个点,就走*/{path.r=CurrentRow;path.c=CurrentCol;/*计入该步*/step++;if((CurrentRow==ResultRow)&&(CurrentCol==ResultCol))/*如果已到达目的地*/{ResultFlag=true;printf("路径如下:\n\n");for(j=0;j《step;j++)printf("第%d步:\t%d\t%d\n",j,path.c);returntrue;}else{if(step》=ROW*COL)/*如果已经走遍了地图,就宣布失败*/return0;if(!ResultFlag)GettingPath(step,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay);/*没有到达目的,继续走*/}}else/*如果已经走过这一点,退回去*/{CurrentRow-=Move;CurrentCol-=Move;;}}else/*如果该点不可走,退回去*/{CurrentRow-=Move;CurrentCol-=Move;;}}else/*如果该步出地图了,退回去*/{CurrentRow-=Move;CurrentCol-=Move;;}}if(ResultFlag)returntrue;returnfalse;/*无路可走*/}
c语言的迷宫问题
//寻路_带野唯权重_带障碍_最短_文件地图_不闪------wlfryq------//#include 《stdio.h》#include 《stdlib.h》#include 《string.h》#include 《windows.h》typedef struct{int x;int y;} _PT;_PT pt;int row=0,col=0;//设置CMD窗口光标位置局慧void setxy(int x, int y){ COORD coord = {x, y}; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);}//获取当前CMD当前光标所在位置void getxy(){HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); COORD coordScreen = {0, 0}; //光标位置 CONSOLE_SCREEN_BUFFER_INFO csbi; if (GetConsoleScreenBufferInfo(hConsole, &csbi)) { pt.x=csbi.dwCursorPosition.X; pt.y=csbi.dwCursorPosition.Y; }}typedef struct{int x;int y;int type;int v;}PT;PT **s=NULL,stack,start,end,c;int pos=0;void prt(){int i,j;system("cls"颂腊培);for(i=0;i《row;i++){for(j=0;j《col;j++){if(s.type==1){printf("■");}else if(i==end.x && j==end.y){printf("★");}else if(i==c.x && j==c.y){printf("◎");}else{printf(" ");}}printf("\n");}Sleep(500);}void stack_in(PT a){stack=a;}PT stack_out(){int i;PT t;t=stack;for(i=0;i《pos-1;i++){stack;}pos--;return t;}void fun(){PT a;int x,y,v;while(1){if(pos==0){break;}a=stack_out();x=a.x;y=a.y;if(x==start.x && y==start.y){break;}v=s.v;if(x-1》=0 && s.v》v+1)){s.v=v+1;stack_in(s);}if(x+1《=row-1 && s.v》v+1)){s.v=v+1;stack_in(s);}if(y-1》=0 && s.v》v+1)){s.v=v+1;stack_in(s);}if(y+1《=col-1 && s.v》v+1)){s.v=v+1;stack_in(s);}}}void go(int x, int y){printf("\n按任意键开始\n");getchar();int v;while(1){if(x==end.x && y==end.y){setxy(0,y+2);printf("end....");return;}v=s.v;if(v==0){return;}if(x-1》=0 && s.v==v-1){c=s;setxy(y*2,x);x=x-1;printf(" ");setxy(y*2,x);printf("◎");Sleep(500);continue;}else if(x+1《=row-1 && s.v==v-1){c=s;setxy(y*2,x);x++;printf(" ");setxy(y*2,x);printf("◎");Sleep(500);continue;}else if(y-1》=0 && s.v==v-1){c=s;setxy(y*2,x);y--;printf(" ");setxy(y*2,x);printf("◎");Sleep(500);continue;}else if(y+1《=col-1 && s.v==v-1){c=s;setxy(y*2,x);y++;printf(" ");setxy(y*2,x);printf("◎");Sleep(500);continue;}}printf("\nreturn go\n");system("pause");}void GetMapFromFile(){int i,j,x,y,len;char ch={’\0’};FILE* fp=fopen("e:\\map1.txt","r");if(fp==NULL){printf("open file failed.\n");return;}x=0;while(!feof(fp)){fgets(ch,50,fp);row++;}col=strlen(ch);fseek(fp,0L,SEEK_SET);while(!feof(fp)){fgets(ch,50,fp);if(s==NULL){len=strlen(ch);for(i=len-1;i》0;i--){if(ch!=’1’){ch=’\0’;}else{break;}}len=strlen(ch);s=(PT**)malloc(sizeof(PT*)*row);for(j=0;j《len;j++){*(s+j)=(PT*)malloc(sizeof(PT)*len);}}y=0;for(i=0;i《len;i++){s-48;s.x=x;s.y=y;s.v=-1;y++;}x++;}start=s;end=s;fclose(fp);}int main(){GetMapFromFile();int i,j;int x,y;x=end.x;y=end.y;s.v=0;stack_in(end);fun();c=start;prt();go(start.x,start.y);return 0;}
递归求解:右手扶墙法寻找迷宫出路
右手扶墙链凯法:有这样一个理论,在迷宫中。祥迅右手靠着墙一直不离开,向一个方向一直走。一定能走出迷宫。谨唤此。如果你摸的是一柱子呢..
用递归算法找出迷宫中所有可行的路径
回溯啊、、、int ans,t=0; //ans数组里存的是每一步肢乱裤的解void dfs(int x,int y){ if (x==x0&&y==y0) {print();return ;} //x0 y0是出口坐标 print()是输出一个合法解的函数 这个很 简单你自己写吧 然后是枚举下一步可以到达的陪世点 因为我不知道走的规则所以写不出来 只能先假设xx yy是x、y能到达的一个点吧 你可以用for循环枚举能历简到的点for (xx.....) for (yy....) if (xx,yy满足条件) { t++; ans=xx; ans=yy; dfs(xx,yy) t--; }}
求一个求从迷宫的一点到另一点的最短路径的递归算法
typedef struct node{int i;struct node **nearby;//相邻结点可以有多个,所以这里用指针的指丛袭针} MAPNODE;MAPNODE a,b;int minpath(a,b)//从a结点到b结缺培点可以伏郑唯分成两步,1.从a到b的相邻结点。2.从相邻结点到b结点,这就是一个递归的过程{int dis=0;int min=999999;//一个足够大的数据MAPNODE **p;if(a.i==b.i)//序号相同表示是同一结点,path为0{dis=0;}else{for(p=b.nearby;*p!=0;p++){dis=0;dis+=minpath(a,*p);dis《min?min=dis:;}}return dis;}
设计一迷宫,并对其求解,输出从入口到出口的路径
#include 《stdlib.h》#include 《stdio.h》#include 《conio.h》#define N 20int aa;/*递归用的数组*/int yes=0;/*判断是否找到路线的函数明肆*/int x,n=0;/*x数组是显示路线用的,n是它的下标,也就是走了几次*/void fun1(int (*aa));/*重复赋值函数*/int fun(int (*a),int i,int j);/*递归找路算法函数*/void begain(int (*t));/*开始的随机地图函数*/void pr(int (*t),int nn);/*输出地图函数*/void win(int (*t));/*成功函数*/void lose();/*失败函数*/void main(void)/*主函数*/{int t;begain(t);/*开始*/pr(t,0);/*开始输入地图拆猜*/fun(t,1,1);/*递归找路*/if(yes)win(t);/*成功*/elselose();/*失败*/getch();}void fun1(int (*aa))/*为了不同方式的递归而循环8次*/{int i,j;for(i=0;i《N;i++) for(j=0;j《N;j++) aa;}int fun(int (*a),int i,int j)/*递归找路*/{if(i==N-2&&j==N-2)/*达到目的了*/ { yes=1; return; }a=1;/*走到的地方变为0*/ fun1(aa,a);if(aa==0&&!yes)/*右下,这里开始的8个if是8个方向的递归*/{fun(aa,i+1,j+1); if(yes)/*如果到达目的了再把值给显示路线的数组*/ {x=j;return;}}/*这里激御轿开始的7个函数具体同上函数*/ fun1(aa,a);if(aa==0&&!yes)/*下边*/{fun(aa,i+1,j); if(yes) {x=j;return;}} fun1(aa,a);if(aa==0&&!yes)/*右边*/{fun(aa,i,j+1); if(yes) {x=j;return;}}fun1(aa,a);if(aa==0&&!yes){ fun(aa,i-1,j); if(yes) {x=j;return;}} fun1(aa,a);if(aa==0&&!yes){fun(aa,i-1,j+1); if(yes) {x=j;return;}} fun1(aa,a);if(aa==0&&!yes){fun(aa,i+1,j-1); if(yes) {x=j;return;}} fun1(aa,a);if(aa==0&&!yes){fun(aa,i,j-1); if(yes) {x=j;return;}} fun1(aa,a);if(aa==0&&!yes){fun(aa,i-1,j-1); if(yes) {x=j;return;}}}void begain(int (*t))/*开始的随机地图*/{int i,j;system(cls);randomize();for(i=0;i《N;i++){ for(j=0;j《N;j++) { if(i==0||i==N-1||j==0||j==N-1) t=1; else if(i==1&&j==1||i==N-2&&j==N-2) t=0; else t=random(2); } }}void pr(int (*t),int nn)/*输出地图*/{int i,j,ii;textcolor(RED);gotoxy(1,1);for(i=0;i《N;i++) { for(j=0;j《N;j++) { if(nn!=1)/*一开始的输出*/ printf(%2d,t); else/*胜利后的输出*/ { for(ii=0;ii《n;ii++) { if(x==j) { cprintf(%2d,t); break; } } if(ii《n) continue; if(i==N-2&&j==N-2) cprintf( 0); else printf(%2d,t); } } printf(\n); }}void win(int (*t))/*找到路的话*/{int i,j,ii,jj;for(i=0;i《n-1;i++) for(j=i+1;j《n;j++) if(x) { for(jj=j,ii=i;jj《n;jj++,ii++) {x;} n=n-(j-i); } printf(\nThe way is:\n); for(i=n-1;i》=0;i--)/*应该递归的情况所以应该是反过来输入路线*/ printf(%3d%3d-》,x); printf(%3d%3d\n,N-2,N-2); t=0; pr(t,1);}void lose()/*没路的话*/{ printf(\nNot find way!\n);}
数据结构算法 用C++ 迷宫最短路径
一般迷宫寻路可以用递归的算法,或者用先进后出的栈数据结构实现
用的是深度优先的算法,可以寻找到走出迷宫的路径
但本题要求求出最短的路径,这就要使用广度优先的算法
一般在程序中需要用到先进先出的队列数据结构
下面是程序的代码,主要原理是用到
quei,quej和prep三个数组来构成队列
分别储存路径的行,列坐标和上一个节点在队列中的位置
大致算法如下,右三个嵌套的循环实现
首先是第一个节点进入队列
当队列不空(循环1)
{
遍历队列中每节点(循环2)
{
将八个方向能够走的节点加入队列(循环3)
孝型 }
旧的节点出列
}
#include《iostream》#include《ctime》 using namespace std; #define MAXNUM 50void main() {int m,n,i,j,x;cout《《"请输入迷宫大小"《《endl;cin》》m》》n;int maze;srand((int)time(NULL));for(i=0;i《=m+1;i++){for(j=0;j《=n+1;j++){if(i==0||j==0||i==m+1||j==n+1)maze=1;else{x=rand()%1000;if(x》700){maze=1;} //控制矩阵中1的个数,太多1迷宫很容易走不通else{maze=0;}}cout《《maze《《’ ’;}cout《《endl;}//以上是输入和迷宫生成,一下是走迷宫 int move={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};int *quei=new int;//储存行坐标队列int *quej=new int;//储存列坐标队列int *prep=new int;//储存之前一步在队列中的位置int head,rear,length;//队列头,队列尾,队列长度head=0;rear=1;length=1;quei=-1;//入口位置进队列int pos;//当前节点在队列中的位置,int ii,jj,ni,nj;//当前节点的坐标,新节点的坐拆慎歼标int dir;//移动方向if(maze==1)length=0;//第一点就不能通过else maze=1;while(length)//队列非空继续{for(pos=head;pos《head+length;pos++)//寻找这一层所有节点{ii=quei;//当前位置坐标if(ii==m&&jj==n)break;for(dir=0;dir《8;dir++)//寻找8个方向{ni=ii+move;//新坐标if(maze==0)//如果没有走过{quei=pos;//新节点入队rear=rear+1;maze=1;//标记已经走过}}}if(ii==m&&jj==n)break;head=head+length;length=rear-head;//这一层节点出列}if(ii==m&&jj==n){while(pos!=-1){cout《《’(’《《quei《《’)’;pos=prep;if (pos!=-1)cout《《’,’;}}else{cout《《"THERE IS NO PATH."《《旅冲endl;}delete quei;delete quej;delete prep;}
求解c语言一递归迷宫问题
给你给伪算法:(设坐标为x,y,坐标向右和下延生。)函脊态数:{困乎 判断当前是不汪野悉是(7,7),如果是,表示走出迷宫。打印轨迹 1 尝试往左先走一步(x-1,如果x小于0,或者对应位置标识为阻塞) 2 1如果成功,用本函数递归调用左走一步的坐标,并记下当前位置到轨迹列表。 3 尝试往前先走一步(y+1,如果y小于0,或者对应位置标识为阻塞) 4 3如果成功,用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。 5 尝试往右先走一步(x+1,如果x小于0,或者对应位置标识为阻塞) 6 5如果成功,用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。 如果是(0,0),表示没有合适的路径可走出迷宫。 如果不是(0,0),将轨迹列表最后一位弹出。}