就是一个简单的bfs的问题,这里用队列来解决问题,有栈来输出路径。
#include"iostream" #include"stdio.h" #include"algorithm" #include"queue" #include"string.h" #include"cmath" #include"stack" using namespace std; int visited[100][100]; char g[100][100]; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int m,n,sx,sy,ex,ey; struct node { int x,y; }; bool judge(int x,int y) { if(x>=0&&x<m&&y>=0&&y<n&&g[x][y]!=‘#‘) return true; return false; } void bfs() { node cur,next; queue<node>q; stack<node>p; cur.x=sx,cur.y=sy; q.push(cur); int i; while(!q.empty()) { cur=q.front(); q.pop(); if(cur.x==ex&&cur.y==ey) { p.push(cur); cout<<"the shortest path is:"; cout<<visited[cur.x][cur.y]<<endl; cout<<"the path is:"; while(visited[cur.x][cur.y]!=0) { for(i=0;i<4;i++) { next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; if(visited[next.x][next.y]+1==visited[cur.x][cur.y]) {p.push(next);break;} } cur.x=next.x;cur.y=next.y; } while(!p.empty()) { cur=p.top(); p.pop(); cout<<"("<<cur.x<<","<<cur.y<<")"; if(cur.x!=ex||cur.y!=ey) cout<<"->"; } cout<<endl; return; } for(i=0;i<4;i++) { next.x=dir[i][0]+cur.x; next.y=dir[i][1]+cur.y; if(judge(next.x,next.y)) { if(visited[next.x][next.y]>visited[cur.x][cur.y]+1) { visited[next.x][next.y]=visited[cur.x][cur.y]+1; q.push(next); } } } } cout<<"no way!"<<endl; } int main() { int i,j; while(1) { cin>>sx>>sy>>ex>>ey; cin>>m>>n; for(i=0;i<m;i++) { getchar(); for(j=0;j<n;j++) { visited[i][j]=m+n+1; cin>>g[i][j]; } } visited[sx][sy]=0; bfs(); } return 0; }
原文:http://www.cnblogs.com/acm-jing/p/4403798.html