algo3-5.zip_最优路径

#include<stdio.h> #include<stdlib.h> #define M 6 #define N 6 #define MaxSize 1000 int mg[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,1}, {1,1,1,1,1,1,1,1,1,1} }; typedef struct { int i,j,step; }Stack; typedef struct { int length; Stack data[MaxSize]; }StType; StType spath[MaxSize]; int kind=-1; void mgpath(int xi,int yi,int xe,int ye,StType path) { int i,j,k,di; if(xi==xe && yi==ye) { kind++; path.data[path.length].i=xi; path.data[path.length].j=yi; path.length++; spath[kind]=path; printf("The NO.%d Path is :\n",kind+1); for(k=0;k<path.length;k++) { printf("(%d,%d)\t",path.data[k].i,path.data[k].j); if((k+1)%5==0) printf("\n"); } printf("\n"); } else { if(mg[xi][yi]==0) { di=0; while(di<4) { path.data[path.length].i=xi; path.data[path.length].j=yi; path.length++; switch(di) { case 0: i=xi-1; j=yi; break; case 1: i=xi; j=yi+1; break; case 2: i=xi+1; j=yi; break; case 3: i=xi; j=yi-1; break; } //if(mg[i][j]==0) //{ mg[xi][yi]=-1; mgpath(i,j,xe,ye,path); //} mg[xi][yi]=0; path.length--; di++; } } } } void printshort() { int i,hit,k=0; int minstep=spath[0].length; for(i=1;i<kind+1;i++) { if(spath[i].length<minstep) minstep=spath[i].length; } i=0; while(i<kind+1) { if(spath[i].length==minstep) { k++; printf("The SHORTEST Path NO.%d is :\n",k); for(hit=0;hit<minstep;hit++) { printf("(%d,%d)\t",spath[i].data[hit].i,spath[i].data[hit].j); if((hit+1)%5==0) printf("\n"); } printf("\n"); } i++; } } void main() { int e; StType path; for(e=0;e<MaxSize;e++) spath[e].length=0; path.length=0; mgpath(1,1,8,8,path); printshort(); scanf("%d",&e); }