懒得写新的XD 直接转录两年前写的教学文 期中考期间 大家应该还有很多科要念吧 偷懒的可以把程式抓下来 把地图size(阵列大小根判断的地方) 从25改成15 (我会闭一只眼改程式的XD) 想试试看但没头绪的 可以看说明的部份 然後自己写看看 期中考加油耶 ps: 我们那届没有交 fstream 所以下面的档案输入输出是 fopen 作者 yantchen (球童Yanting) 看板 NTUE-CS99 标题 [课业] 走迷宫程式参考 时间 Wed Oct 31 23:59:29 2007 ─────────────────────────────────────── 抱歉，今天早上临时写出来的有一些bug，已经修正 http://stu.ntue.edu.tw/~s9516009/maze.rar 里面有 6 个档案 mapmaker.exe 会乱数产生25x25地图档 map.txt (起点终点一定是0；其他格乱数产生0或1，不一定有路可以走) map.txt 这个rar附赠的地图档 经过测试有路可以走 map_method1.cpp 顺时钟走法迷宫程式档 (下面会详细讲解这个程式) map_method1.exe 顺时钟走法迷宫执行档 map_method2.cpp 填数字走法迷宫程式档 (我自己的解法，另外一种演算法，仅供参考) map_method2.exe 填数字走法迷宫执行档 ============================================================================= map_method1.cpp 顺时钟走法的演算法： 1.顺时针检查八个方向 有路就走(不管是不是死路) 没路(墙壁或走过)就转下一个方向 把走到的那一个 x、y、方向 三个东西放到堆叠 2.如果某一格八个方向都试过没有路可以走 从堆叠弹出上一步的 x、y、方向 并回到步骤1尝试下一个方向 3.重复步骤1、2，如果 x、y = 终点 就跳出回圈 输出路径 如果堆叠没有东西可以弹出了 就是无解 ( 一开始记得把起点放到堆叠里面 如果起点被弹出来後还是死路 还要再谈出堆叠找上一步 就知道是无解 ) 宣告堆叠： step是用阵列作成的堆叠 有1000个空间(其实25x25就够了) 每个空间可以放3样资讯 x、y、方向 s是记录堆叠顶端的变数 push是把x、y、方向放入堆叠的函数 pop是把x、y、方向取出堆叠的函数 show是把堆叠从0到top输出(show出路径)的函数 class stack{ int step[1000][3]; int s; public: stack(){ s=0; } void push(int x,int y,int d){ step[s][0]=x; step[s][1]=y; step[s][2]=d; s++; } int pop(int &x,int &y,int &d){ s--; if(s==0) return -1; x=step[s-1][0]; y=step[s-1][1]; d=step[s-1][2]; } void show(){ for(int i=0;i<s;i++) cout<<"第"<<i+1<<"步"<<"("<<step[i][0]<<","<<step[i][1]<<")\n"; } }; 主程式部份 int main(){ 宣告二维阵列map存放地图 为了避免判断有没有超出地图范围的麻烦 把阵列设成27x27 并把多的四边设成墙壁 所以地图实际存放在阵列的区域是(1,1)~(25,25) int map[27][27]; 读档，请参考一下程设投影片 for(int j=0;j<27;j++) for(int i=0;i<27;i++) map[i][j]=1; FILE* f=fopen("map.txt","r"); char buf[25]; for(int j=1;j<=25;j++){ fgets(buf,30,f); for(int i=0;i<25;i++) map[i+1][j]=buf[i]-'0'; } fclose(f); 宣告变数： stk存放路径堆叠；x,y目前所在位置；d目前尝试方向；xt,yt下一步预计要往那里走 stack stk; int x=1,y=1,d=0,xt,yt; 起点设定： 把起点放进堆叠(方便之後判断是否无解) 地图上0是路；1是墙壁；2是走过的路；3是死路 stk.push(x,y,d); map[x][y]=2; do{ 方向设定： d=0~7 分别代表一个方向 用switch算出这个方向的下一步 存在xt、yt里面 switch(d){ case 0: xt=x+1; yt=y-1; break; // 右上 case 1: xt=x+1; yt=y; break; // 右 case 2: xt=x+1; yt=y+1; break; // 右下 case 3: xt=x; yt=y+1; break; // 下 case 4: xt=x-1; yt=y+1; break; // 左下 case 5: xt=x-1; yt=y; break; // 左 case 6: xt=x-1; yt=y-1; break; // 左上 case 7: xt=x; yt=y-1; break; // 上 } 如果可以走 (地图=0) x,y,d丢入堆叠 地图设2 走到下一格d归零 if(map[xt][yt]==0){ x=xt; y=yt; stk.push(x,y,d); map[x][y]=2; d=0; } else { 不能走就转下一个方向(d++) d++; } 若d加到超过8 想必是遇到了转了一圈都找不到路的死路 弹出上一步 转下一个方向 并把死路这格设成3 k用来存pop的传回值 上面的pop函数设定没有东西可以弹出得时候传回-1 判断k=-1的时候 输出无解 并结束程式 if(d>=8){ map[x][y]=3; int k=stk.pop(x,y,d); if(k==-1){ cout<<"没有路可以走喔\n"; system("pause"); return 0; } d++; } 走到终点才跳出回圈 走完後先用座标显示走过路径 再用地图显示走过路径 }while(x!=25||y!=25); stk.show(); for(int j=1;j<=25;j++){ for(int i=1;i<=25;i++){ if(map[i][j]==1) cout<<"█"; else if(map[i][j]==2) cout<<"‧"; else cout<<"　"; } cout<<endl; } system("pause"); } --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 203.68.15.99 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 120.127.36.183 ※ 编辑: yantchen 来自: 120.127.36.183 (11/08 20:29) ※ 编辑: yantchen 来自: 120.127.36.183 (11/08 20:33)