文章目錄
- 一、 目的與要求
- 二、 問題描述和求解方法
- 三、 解題過程
- 四、 實現源碼
- 五、 相關案例
- 案例一
- 案例二
一、 目的與要求
1、目的：
通過布置具有一定難度的實際程序設計項目，使學生進一步理解和掌握課堂上所學各種基本抽象數據類型的邏輯結構、存儲結構和操作實現算法，以及它們在程序中的使用方法；使學生掌握分析問題，求解問題的方法并提高學生設計編程實現的能力。
2、要求： 基本要求：
1.要求利用C\C++語言來完成系統的設計；
2.突出C語言的函數特征（以多個函數實現每一個子功能）或者C++語言面向對象的編程思想；
3.畫出功能模塊圖；
4.進行簡單界面設計，能夠實現友好的交互；
5.具有清晰的程序流程圖和數據結構的詳細定義；
6.熟練掌握C語言或者C++語言的各種操作。創新要求： 在基本要求達到后，可進行創新設計，如系統用戶功能控制，改進算法的實現，實現友好的人機交互等等
二、 問題描述和求解方法
1 、問題描述（功能要求）：
可以任意定義一個迷宮，用非遞歸的方法求出走出迷宮的通路，并把路徑輸出出來。
要求： 存儲結構、基本算法（可以使用程序流程圖）、源程序、測試數據和結果、算法的 時間復雜度、另外可以提出算法的改進方法。
1) 迷宮的存儲結構要合理；
2) 應該考慮算法的時間和空間復雜度。
3) 當確定迷宮的規模以及形態以后要把至少一條能走出迷宮的路徑輸出出來；
4)程序應當滿足正確性、可讀性、健壯性和高效率及低存儲量等目標要求，遵循代碼規 范，方便調試和閱讀。
2 、問題的解決方案：
根據系統功能要求，可以將問題解決分為以下步驟：
（ 1 ）迷宮可以采用二維數組來存儲，迷宮的通路狀態可以用不同的字符來表示；
（ 2 ）根據問題描述，設計算法的實現；
（ 3 ）建議在解決問題時要采用棧或者隊列數據結構；
（ 4 ）完成算法的各個功能模塊；
（ 5 ）功能調試；
（ 6 ）完成系統總結報告以及系統使用說明書。
三、 解題過程
1.分析程序的功能要求，劃分程序功能模塊。
2.畫出系統流程圖。
3.代碼的編寫。定義數據結構和各個功能子函數。
4.程序的功能調試。
5.完成系統總結報告以及使用說明書
四、 實現源碼
#include<iostream>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 1005;
int n,m,b,c,starx,stary,endx,endy,a[MAXN][MAXN],book[MAXN][MAXN],ans,flag1,flagsee;
int minn = 999999,num,flagY=1;struct node{int x,y;int s; //x,y為坐標，s為步數 int fx,fy;//fx,fy代表該點前面的點的坐標
};
node bfsmin[MAXN];
node minfinal[MAXN];
stack<node> st;
stack<node> minst;
queue<node> que;
node MAP,head,tail;
node minMAP[MAXN];
node otherMAP[MAXN];
int flag=0,minflag=1;
void outmap(stack<node> st)//輸出可行方案數
{printf("可行方案%d:",++flag);int ans1 = 0;while(!st.empty()){otherMAP[ans1++] = st.top();st.pop(); }//printf("(%d,%d)",starx,stary);cout<<"起始點"; for(int i = ans-1;i>0;i--){printf("->(%d,%d)",otherMAP[i].x,otherMAP[i].y);if((ans-i) != 0 && (ans-i) % 10 == 0)printf("\n");}cout<<"->終止點"; cout<<endl;
}
void outmin(node bfsmin[MAXN],int minflag)
{int find = minflag;int tx = bfsmin[find].fx;int ty = bfsmin[find].fy;int x=0,y=0; while(bfsmin[find].fx != -1 || bfsmin[find].fy!=-1){int y = 0 ;for(int i=1;i<=minflag;i++){if(bfsmin[i].x == tx&& bfsmin[i].y == ty){minfinal[x++] = bfsmin[i];find = i;tx = bfsmin[i].fx;ty = bfsmin[i].fy;if(x%10 == 0){y = 1;break;}}}if(y==1)break;}cout<<"☆最短路徑長度為："<<x<<endl; cout<<"☆最短路徑為："<<endl;for(int i=x-1;i>=0;i--){printf("(%d,%d)->",minfinal[i].x,minfinal[i].y);}printf("(%d,%d)",endx,endy);
}
void outseeing(stack<node> st)//所有可行方案的可視圖
{while(!st.empty()){a[st.top().x][st.top().y] = 2;st.pop();}printf("可行方案%d:\n",++flagsee); for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j] == 2){if(i == endx && j == endy)cout<<"★"; elsecout<<"□";a[i][j] = 0;} else if(a[i][j] == 0){if(i == starx && j == stary)cout<<"◆";elsecout<<"█";}else if(a[i][j] == 1)cout<<"▓";}cout<<endl;}cout<<endl;
}
void outminseeing(node bfsmin[MAXN],int minflag)//最短路徑的可視圖
{ int x = 0;int find = minflag;int tx = bfsmin[find].fx;int ty = bfsmin[find].fy;while(bfsmin[find].fx != -1 || bfsmin[find].fy!=-1){int y = 0 ;for(int i=1;i<=minflag;i++){if(bfsmin[i].x == tx&& bfsmin[i].y == ty){minfinal[x++] = bfsmin[i];find = i;tx = bfsmin[i].fx;ty = bfsmin[i].fy;if(x%10 == 0){y = 1;break;}}}if(y==1)break;}cout<<"☆最短路徑長度為："<<x<<endl; ; cout<<"☆最短路徑為："<<endl;for(int i = x-1;i>=0;i--)a[minfinal[i].x][minfinal[i].y] = 2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j] == 2){if(i==starx && j==stary)cout<<"★";elsecout<<"□";a[i][j] = 0;}else if(a[i][j] == 0){if(i == endx && j == endy)cout<<"◆";elsecout<<"█";}else if(a[i][j] == 1)cout<<"▓";}cout<<endl;}
}
void dfs(int midx,int midy,int step)//深度優先搜索 (dfs)
{int nx,ny;if(midx == endx && midy == endy){if(minn > step){minn = step;flagY = 1;//flag1 = copyMAP(st);} if(num == 2) outmap(st);if(num == 4) outseeing(st);return ; }int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}};for(int i=0;i<4;i++){nx = midx+next[i][0];ny = midy+next[i][1];if(nx>n||nx<1||ny>m||ny<1)continue;if(a[nx][ny]==0&&book[nx][ny]==0){MAP.x = nx; MAP.y = ny;ans++;st.push(MAP);//cout<<ans<<" ";book[nx][ny]=1;dfs(nx,ny,step+1);book[nx][ny]=0;st.pop();ans--;}} return ;
}void bfs()//廣度優先搜索
{int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int bfsflag = 0,tx,ty;head.x = tail.x = starx;head.y = tail.y = stary;head.fx = tail.fx = -1;head.fy = tail.fy = -1; head.s = tail.s = 0;que.push(head);bfsmin[minflag++] = que.front();while(!que.empty()){for(int i=0;i<4;i++){tx = que.front().x + next[i][0];ty = que.front().y + next[i][1];if(tx>n||tx<1||ty>m||ty<1)continue;if(a[tx][ty] == 0 && book[tx][ty] == 0){book[tx][ty] = 1;tail.x = tx; tail.y = ty;tail.fx = que.front().x;tail.fy = que.front().y;tail.s = que.front().s + 1;que.push(tail);}if(tx == endx && ty == endy){bfsflag = 1;bfsmin[minflag++] = tail;if(num == 3)outmin(bfsmin,minflag-1);else if(num == 5)outminseeing(bfsmin,minflag-1);break;}}que.pop();bfsmin[minflag++] = que.front();if(bfsflag == 1)break;}
}
int main()
{cout<<"\n";cout<<"\t\t 歡迎使用迷宮程序"<<endl; cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl;cout<<"☆☆\t\t\t1.輸入迷宮地圖\t\t\t☆☆"<<endl;cout<<"☆☆\t\t2.尋找兩個點在迷宮的所有可行方案\t☆☆"<<endl;cout<<"☆☆\t\t 3.尋找兩點在迷宮中的最短路徑\t\t☆☆"<<endl; cout<<"☆☆\t 4.尋找兩個點在迷宮的所有可行方案的可視圖 ☆☆"<<endl;cout<<"☆☆\t\t5.尋找兩點在迷宮中的最短路徑的可視圖 \t☆☆"<<endl;cout<<"☆☆\t\t\t6.結束操作\t\t\t☆☆"<<endl;cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl;cout<<"☆輸入對應數字實現相應功能："<<endl; while(cin>>num){int flagnum = 0;switch(num){case(1):{cout<<"☆輸入迷宮的長和寬："<<endl;cin>>n>>m;cout<<"☆輸入迷宮地圖：";cout<<"(其中0代表可走；1代表為障礙物，不可走)"<<endl; for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}cout<<"☆輸入成功,輸入其他數字執行替他操作"<<endl; break;}case(2):{memset(book,0,sizeof(book));cout<<"☆輸入起點坐標："<<endl; cin>>starx>>stary;book[starx][stary]=1;cout<<"☆輸入終點坐標："<<endl;cin>>endx>>endy;dfs(starx,stary,0);if(a[starx][stary]==1 || a[endx][endy]==1)flagY=0;if(flagY == 0)cout<<"沒有可行路徑,或者坐標超出迷宮范圍！！"<<endl; cout<<"☆操作成功,輸入其他數字執行替他操作"<<endl;break;}case(3):{memset(book,0,sizeof(book));cout<<"☆輸入起點坐標："<<endl; cin>>starx>>stary;book[starx][stary]=1;cout<<"☆輸入終點坐標："<<endl;cin>>endx>>endy;if(a[starx][stary]==1 || a[endx][endy]==1)flagY=0;if(flagY == 0)cout<<"沒有可行路徑,或者坐標超出迷宮范圍！！"<<endl;else if(starx == endx && stary == endy)cout<<"☆最短路徑長度為：0"<<endl;else{bfs();cout<<endl;cout<<"☆操作成功,輸入其他數字執行替他操作"<<endl;} break;}case(4):{memset(book,0,sizeof(book));cout<<"☆輸入起點坐標："<<endl; cin>>starx>>stary;book[starx][stary]=1;cout<<"☆輸入終點坐標："<<endl;cin>>endx>>endy;cout<<"◆代表起始點\t★代表終止點"<<endl; cout<<"□代表該方案中要走的位置"<<endl;cout<<"█代表迷宮中可走的位置，但該方案中未走的位置"<<endl;cout<<"▓代表迷宮中不可走的位置"<<endl; cout<<endl;dfs(starx,stary,0);if(a[starx][stary]==1 || a[endx][endy]==1)flagY=0;if(flagY == 0)cout<<"沒有可行路徑,或者坐標超出迷宮范圍！！"<<endl; else cout<<"☆操作成功,輸入其他數字執行替他操作"<<endl;break; } case(5):{memset(book,0,sizeof(book));cout<<"☆輸入起點坐標："<<endl; cin>>starx>>stary;book[starx][stary]=1;cout<<"☆輸入終點坐標："<<endl;cin>>endx>>endy;cout<<"◆代表起始點\t★代表終止點"<<endl; cout<<"□代表該方案中要走的位置"<<endl;cout<<"█代表迷宮中可走的位置，但該方案中未走的位置"<<endl;cout<<"▓代表迷宮中不可走的位置"<<endl; cout<<endl;dfs(starx,stary,0);if(a[starx][stary]==1 || a[endx][endy]==1)flagY=0;if(flagY == 0)cout<<"沒有可行路徑,或者坐標超出迷宮范圍！！"<<endl;else if(starx == endx && stary == endy)cout<<"☆最短路徑長度為：0"<<endl;else{bfs(); cout<<"☆操作成功,輸入其他數字執行替他操作"<<endl; }break;} case(6):{flagnum = 1;cout<<"\t☆操作結束☆"<<endl; break;}default:{cout<<"☆未找到對應的功能，請正確輸入與相關操作對應的數字"<<endl; break;}} if(flagnum == 1)break;}return 0;
}
/*
5 4
1 1
4 3
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
*/五、 相關案例
案例一
#include <iostream>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std; int dx[4]={0,-1,1,0};//方向
int dy[4]={-1,0,0,1};
bool vis[6][6];
int total=0;//多少可到達路徑
int sx=1,sy=1;//入口出口坐標
int ex=4,ey=4;
int num[10][10];//廣搜時記錄到達當前點的最少步數 struct P
{ int x,y;
}point[40];//用來記錄可到達路徑 struct PP
{ int fx,fy;
}path[10][10];//用來記錄最短路徑坐標增量，用于回溯輸出最短路徑 char map[6][6]=//地圖
{ {'#','#','#','#','#','#'}, {'#','.','.','.','#','#'}, {'#','.','#','.','.','#'}, {'#','.','.','.','#','#'}, {'#','#','.','.','.','#'}, {'#','#','#','#','#','#'}
}; bool ok(int x,int y)//判斷當前點是否可走
{ if(x<0||x>5||y<0||y>5) return 0; if(map[x][y]=='#') return 0; if(vis[x][y]==1) return 0; return 1;
} void dfs(int x,int y,int step)//深搜可到達路徑，參數step對于記錄路徑來說很重要
{ if(x==ex&&y==ey) { total++; cout<<"第"<<total<<"條路徑為: "; for(int i=0;i<step;i++) cout<<"("<<point[i].x<<","<<point[i].y<<")"; cout<<endl; return; } for(int i=0;i<4;i++) { int curx=x+dx[i]; int cury=y+dy[i]; if(ok(curx,cury)) { vis[curx][cury]=1; point[step].x=curx;point[step].y=cury;//記錄路徑 dfs(curx,cury,step+1); vis[curx][cury]=0; } }
} void bfs(int x,int y)//廣搜求最短路徑
{ num[x][y]=0; queue<P>q; P a,b; a.x=x; a.y=y; path[a.x][a.y].fx=0;path[a.x][a.y].fy=0; q.push(a); while(!q.empty()) { b=q.front(); q.pop(); for(int i=0;i<4;i++) { a.x=b.x+dx[i]; a.y=b.y+dy[i]; if(ok(a.x,a.y)) { vis[a.x][a.y]=1; q.push(a); path[a.x][a.y].fx=dx[i]; path[a.x][a.y].fy=dy[i]; num[a.x][a.y]=num[b.x][b.y]+1;//記錄步數 } } }
} void print(int x,int y)//輸出最短路徑
{ if(x==sx&&y==sy) { cout<<"(1,1)"; return; } print(x-path[x][y].fx,y-path[x][y].fy); cout<<"("<<x<<","<<y<<")";
}
int main()
{ memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); vis[sx][sy]=1; point[0].x=sx;point[0].y=sy; dfs(sx,sy,1); cout<<"總計有"<<total<<"條可到達路徑"<<endl; memset(vis,0,sizeof(vis)); vis[sx][sy]=1; bfs(sx,sy); cout<<"到達各個點的最少步數如下:"<<endl<<endl; for(int i=0;i<6;i++) { for(int j=0;j<6;j++) cout<<num[i][j]<<" "; cout<<endl; } cout<<endl; cout<<"最少要走"<<num[ex][ey]<<"步才能走到出口"<<endl<<endl;; cout<<"其中一條最短路徑為:";print(ex,ey);cout<<endl; return 0;
}
案例二
#include<iostream>
using namespace std;void EnQueue(int i,int j,int k); //入隊一個節點
void DeQueue(int *i,int *j,int *k); //獲取當前節點的序號和對應的迷宮坐標，然后出列
bool GetNextPos(int *i ,int *j,int count); //得到下一個鄰接點的位置
void ShortestPath_BFS(int i,int j); //廣度優先遍歷尋找最短路徑
void ShortestPath(); //輸出最短路徑
void Print(); //輸出迷宮形狀int Map[10][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,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,0},{1,1,1,1,1,1,1,1,1,1}
};struct Node {int parent_id; //保存父節點的位置int node_id; //當前節點的序號，以便傳遞給孩子節點int x,y; //當前結點對應的坐標
} Q[10*10]; //每個節點包含迷宮坐標、隊列中的序號、父節點的序號，多個節點形成隊列int front = 0,rear = 0; //隊列頭指針和尾指針int main() {cout<<"程序說明："<<'\n'<<"1.輸出路徑為最短路徑；"<<'\n'<<"2.默認的出口在最右下角，如有需要可以調整。"<<'\n'<<'\n';cout<<"初始地圖如下："<<endl;Print();int i,j;reinput:cout<<"請輸入起點坐標（x,y）： "<<endl;cin>>i>>j;if(Map[i][j]) {cout<<"不能從該處出發，請重新輸入！"<<endl;goto reinput;}ShortestPath_BFS(i,j);cout<<"最短路徑之一如下："<<endl;ShortestPath();
}void EnQueue(int i,int j,int k) { //入隊一個節點Q[rear].x = i;Q[rear].y = j; //保存當前節點對應的坐標位置Q[rear].parent_id = k; //保存父節點的序號 ************-1Q[rear].node_id = rear; //保存當前節點序號rear++;
}void DeQueue(int *i,int *j,int *k) { //獲取當前節點的序號和對應的迷宮坐標，然后出列*i = Q[front].x;*j = Q[front].y;*k = Q[front].node_id;front++; //出列一個節點
}bool GetNextPos(int *i ,int *j,int count) { //得到下一個鄰接點的位置switch(count) {case 1:(*j)++;return 1; //右case 2:(*i)++;return 1; //下case 3:(*j)--;return 1; //左case 4:(*i)--;return 1; //上default:return 0;}
}void ShortestPath_BFS(int i ,int j) { //廣度優先遍歷尋找最短路徑int count,m,n,k;EnQueue(i,j,-1);Map[i][j] = 1; //起點入隊，標記起點已走過while(true) {count = 1;DeQueue(&i,&j,&k);n = i,m = j;
//保存當前位置while(GetNextPos(&i,&j,count)) {count++;if(!Map[i][j]) {EnQueue(i,j,k);Map[i][j] = 1;if(i == 8 && j == 9)return; //到達終點（8,9）是默認終點，可以任意修改}i = n;j = m; //保證遍歷當前坐標的所有相鄰位置}}}void ShortestPath() {int i,j,k,sum=0;k = rear-1;while(k != -1) {i = Q[k].x;j = Q[k].y;Map[i][j] = 2;k = Q[k].parent_id;}cout<<" 0 1 2 3 4 5 6 7 8 9"<<endl;for(i = 0; i < 10; i++) {cout<<i;for(j = 0; j < 10; j++) {if(Map[i][j]==2) {sum++;cout<<"□";} elsecout<<"■";}cout<<endl;}cout<<"最短路徑長度："<<sum<<endl;
}void Print() {cout<<" 0 1 2 3 4 5 6 7 8 9"<<endl;for(int i = 0; i < 10; i++) {cout<<i;for(int j = 0; j < 10; j++) {if(Map[i][j])cout<<"■";elsecout<<"□";}cout<<endl;}
}
的作用)
