migong.rar_migong_多功能

#include <iostream.h> const int m=6,n=8; int mark[m+2][n+2]; int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{1,-1}}; int maze[m+2][n+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,1}, {1,1,0,0,1,1,1,1,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,1,1,0,1,1,1,1,1,1}, {1,0,0,0,0,0,1,0,1,1}, {1,1,0,1,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; int w=0,l=0; int a[n*m][2],c[n*m][2]; int seekpath(int x,int y ) { int i,g,h; if((x==m)&&(y==n)) return 1; for(i=0;i<8;i++) { g=x+move[i][0]; h=y+move[i][1]; if((maze[g][h]==0)&&(mark[g][h]==0)) { mark[g][h]=-1; if(seekpath(g,h)) { a[l][0]=g; a[l][1]=h; l++; cout<<"("<<g<<","<<h<<")，"; return 1; } } } if((x==1)&&(y==1)) cout<<"No path!"<<endl; return 0; } int seekpath2(int x,int y ) { int i,g,h,j; if((x==m)&&(y==n)) return 1; for(i=0;i<8;i++) { g=x+move[i][0]; h=y+move[i][1]; if((maze[g][h]==0)&&(mark[g][h]!=-2)) { mark[g][h]=-2; if(seekpath2(g,h)) { a[l][0]=g; a[l][1]=h; l++; return 1; } } } if((x==c[w][0])&&(y==c[w][1])) return 0; return 0; } void main( ) { int i,j,h,y,x; for(i=0;i<m+2;i++) { cout<<endl; for(j=0;j<n+2;j++) cout<<maze[i][j]<<" "; } cout<<endl; //初始化数组 for(i=0;i<m+2;i++) for(j=0;j<n+2;j++) mark[i][j]=0; mark[1][1]=-1; cout<<"其中一条路径为："<<endl; if(seekpath(1,1)) { a[l][0]=1; a[l][1]=1; cout<<"(1,1)"<<endl; for(i=0;i<=l;i++) for(j=0;j<2;j++) c[i][j]=a[i][j]; for(w=l;w>=0;w-- ) { h=w; if(c[h][0]==-100||c[h][1]==-100) break; i=w-1; j=c[i][1]; i=c[i][0]; mark[i][j]=-2; h=l; l=0; if (seekpath2(c[w][0],c[w][1])) { l--; j=w-1; if(l<h) { for( ;l>=0;l--,j--) for(i=0;i<2;i++) c[j][i]=a[l][i]; for( ;j>=0;j--) for(i=0;i<2;i++) c[j][i]=-100; } } } cout<<"最短路径为："<<endl; for(i=0; ;i++) { if(c[i][0]==0||c[i][1]==0) break; if(c[i][0]!=-100||c[i][1]!=-100) cout<<"("<<c[i][0]<<","<<c[i][1]<<"),"; } } cout<<endl; }