迷宫问题的求解是实验心理学的一个经典问题.，心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多壁障，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了奶酪，吸引老鼠在迷宫中寻找通路以到达出口。设计回溯算法实现迷宫求解。
#include<iostream> #include<vector> #include<queue> using namespace std; vector<vector<int>> mp; vector<pair<int,int>> result,minRoad; int row,col,mycount=0; int mov[8][2]={{1,1},{1,0},{0,1},{1,-1},{-1,1},{0,-1},{-1,0},{-1,-1}}; void print(vector<pair<int,int>>& vc){ for(int i=0;i<vc.size();i++) cout<<(i?" ":"")<<"("<<vc[i].first+1<<","<<vc[i].second+1<<")"; cout<<endl; } void printMinRoad(const int& x,const int& y){ if(x!=0&&y!=0){ printMinRoad(x+mov[8+mp[x][y]][0],y+mov[8+mp[x][y]][1]); cout<<" "; } cout<<"("<<x+1<<","<<y+1<<")"; } void dfs(const int& x,const int& y){ if(x==row-1&&y==col-1){ cout<<"第"<<++mycount<<"种方案："<<endl; print(result); if(minRoad.empty()||result.size()<minRoad.size()) minRoad=result; } else{ for(int i=0;i<8;i++){ int a=x+mov[i][0],b=y+mov[i][1]; if(a>=0&&a<row&&b>=0&&b<col&&mp[a][b]==0){ mp[a][b]=1; result.push_back(make_pair(a,b)); dfs(a,b); result.pop_back(); mp[a][b]=0; } } } } void bfs(){ queue<pair<int,int>> q; q.push(make_pair(0,0)); mp[0][0]=1; while(true){ pair<int,int>& k=q.front(); for(int i=0;i<8;i++){ int a=k.first+mov[i][0],b=k.second+mov[i][1]; if(a>=0&&a<row&&b>=0&&b<col&&mp[a][b]==0){ mp[a][b]=-(i+1); if(a==row-1&&b==col-1){ printMinRoad(row-1,col-1); return ; } q.push(make_pair(a,b)); } } q.pop(); } } int main(){ vector<vector<int>> root = { {0,1,1,1,0,1,1,1}, {1,0,1,0,1,1,1,1}, {0,1,0,0,0,0,0,1}, {0,1,1,1,0,1,1,1}, {1,0,0,1,1,0,0,0}, {0,1,1,0,0,1,1,0} }; row = root.size(); col = root[0].size(); mp=root; mp[0][0]=1; result.push_back(make_pair(0,0)); dfs(0,0); mp=root; cout << endl << "其中最短的路线为：" << endl; print(minRoad); cout << endl << "分支限界法求得最短路线为：" << endl; bfs(); return 0; }
