ZOJ1055-Oh_Those_Achin_Feet.rar_BFS最短路径_ZOJ1055_bfs求最短路径_zoj

#include<cstdio> #include<queue> using namespace std; int N,M; //dep表示最短路径的长度,而total表示最短路径的条数 int dep,total; char map[20][20],source,dest; //表示被最短路径经过多少次,p用来纪录路径 int num[20][20],p_x[80],p_y[80]; int load,sx,sy,dx,dy; //load factor double lf[20][20]; //用bfs求最短路径长度 void short_path(); int main() { int i,j; // freopen("in.txt","r",stdin); // freopen("out.txt","w+",stdout); scanf("%d%d",&M,&N); for(i=0;i<N;i++) scanf("%s",map[i]); for(i=0;i<M;i++) for(j=0;j<N;j++) lf[i][j]=0.0; while(1) { getchar(); if(scanf("%c%c %d",&source,&dest,&load)==EOF || source=='X' || dest=='X') break; //printf("%c %c %d\n",source,dest,load); for(i=0;i<N;i++) for(j=0;j<M;j++) { if(map[i][j]==source) { sx=i; sy=j; } if(map[i][j]==dest) { dx=i; dy=j; } } //printf("sx=%d,sy=%d,dx=%d,dy=%d\n",sx,sy,dx,dy); short_path(); /* for(i=0;i<M;i++) { for(j=0;j<N;j++) printf("%d\t",num[i][j]); printf("\n"); } */ //dfs搜寻所有最短路径 for(i=0;i<M;i++) for(j=0;j<N;j++) if(map[i][j]=='.') lf[i][j]+=num[i][j]*load*1.0/total; } for(i=0;i<M;i++) { printf("%6.2lf",lf[i][0]); for(j=1;j<M;j++) printf(" %6.2f",lf[i][j]); printf("\n"); } return 0; } void short_path() { //准备用bfs来求最短路径长度 queue<int> qx,qy; int d[20][20],tnum[20][20],i,j,tx,ty,td,t; bool mark[20][20]; for(i=0;i<N;i++) for(j=0;j<M;j++) d[i][j]=-1; qx.push(sx) , qy.push(sy) , d[sx][sy]=0; while(1) { tx=qx.front() , ty=qy.front() , td=d[tx][ty]; if(d[dx][dy]!=-1 && td>=d[dx][dy]) break; if(tx-1>=0 && (map[tx-1][ty]=='.' || map[tx-1][ty]==dest) ) { if(d[tx-1][ty]==-1) qx.push(tx-1) , qy.push(ty) , d[tx-1][ty]=td+1; } if(tx+1 <N && (map[tx+1][ty]=='.' || map[tx+1][ty]==dest)) { if(d[tx+1][ty]==-1) qx.push(tx+1) , qy.push(ty) , d[tx+1][ty]=td+1; } if(ty-1>=0 && (map[tx][ty-1]=='.' || map[tx][ty-1]==dest)) { if(d[tx][ty-1]==-1) qx.push(tx) , qy.push(ty-1) , d[tx][ty-1]=td+1; } if(ty+1 <M && (map[tx][ty+1]=='.' || map[tx][ty+1]==dest)) { if(d[tx][ty+1]==-1) qx.push(tx) , qy.push(ty+1) , d[tx][ty+1]=td+1; } qx.pop() , qy.pop(); } dep=d[dx][dy]; // printf("dep=%d\n",dep); //逆推求所有路径数 for(i=0;i<M;i++) for(j=0;j<N;j++) { tnum[i][j]=0; mark[i][j]=false; } while(!qx.empty()) { qx.pop(); qy.pop(); } qx.push(dx) , qy.push(dy) ,tnum[dx][dy]=1 , mark[dx][dy]=true; for(i=dep;i>0;i--) { while(1) { tx=qx.front() , ty=qy.front(); // printf("tx=%d ty=%d\n",tx,ty); if(d[tx][ty]!=i) break; // printf("i=%d\n",i); if(tx-1>=0 && d[tx-1][ty]+1==d[tx][ty]) { tnum[tx-1][ty]+=tnum[tx][ty]; if(!mark[tx-1][ty]) qx.push(tx-1) , qy.push(ty) , mark[tx-1][ty]=true; } if(tx+1 <N && d[tx+1][ty]+1==d[tx][ty]) { tnum[tx+1][ty]+=tnum[tx][ty]; if(!mark[tx+1][ty]) qx.push(tx+1) , qy.push(ty) , mark[tx+1][ty]=true; } if(ty-1>=0 && d[tx][ty-1]+1==d[tx][ty]) { tnum[tx][ty-1]+=tnum[tx][ty]; if(!mark[tx][ty-1]) qx.push(tx) , qy.push(ty-1) , mark[tx][ty-1]=true; } if(ty+1 <M && d[tx][ty+1]+1==d[tx][ty]) { tnum[tx][ty+1]+=tnum[tx][ty]; if(!mark[tx][ty+1]) qx.push(tx) , qy.push(ty+1) , mark[tx][ty+1]=true; } qx.pop() , qy.pop(); } } /* for(i=0;i<M;i++) { for(j=0;j<N;j++) printf("=%d\t",tnum[i][j]); printf("\n"); } */ total=tnum[sx][sy]; // printf("total=%d\n",total); //正推求每点的经过的最短路径数 for(i=0;i<M;i++) for(j=0;j<N;j++) { num[i][j]=0; mark[i][j]=false; } num[sx][sy]=total; while(!qx.empty()) { qx.pop(); qy.pop(); } //qx.pop() , qy.pop(); qx.push(sx) , qy.push(sy) , mark[sx][sy]=true; // printf("haha\n"); for(i=0;i<dep;i++) { while(1) { tx=qx.front() , ty=qy.front(); if(d[tx][ty]!=i) break; // printf("tx=%d ty=%d d=%d num=%d\n",tx,ty,d[tx][ty],num[tx][ty]); t=0; //把周围4个点的儿子为tx ty的点按比例分配 if(tx-1>=0 && d[tx-1][ty]-1==d[tx][ty]) { t+=tnum[tx-1][ty]; if(!mark[tx-1][ty]) qx.push(tx-1) , qy.push(ty) , mark[tx-1][ty]=true; } if(tx+1 <N && d[tx+1][ty]-1==d[tx][ty]) { t+=tnum[tx+1][ty]; if(!mark[tx+1][ty]) qx.push(tx+1) , qy.push(ty) , mark[tx+1][ty]=true; } if(ty-1>=0 && d[tx][ty-1]-1==d[tx][ty]) { t+=tnum[tx][ty-1]; if(!mark[tx][ty-1]) qx.push(tx) , qy.push(ty-1) , mark[tx][ty-1]=true; } if(ty+1 <M && d[tx][ty+1]-1==d[tx][ty]) { t+=tnum[tx][ty+1]; if(!mark[tx][ty+1]) qx.push(tx) , qy.push(ty+1) , mark[tx][ty+1]=true; } // if(t) { if(tx-1>=0 && d[tx-1][ty]-1==d[tx][ty]) num[tx-1][ty]+=tnum[tx-1][ty]*num[tx][ty]/t; if(tx+1 <N && d[tx+1][ty]-1==d[tx][ty]) num[tx+1][ty]+=tnum[tx+1][ty]*num[tx][ty]/t; if(ty-1>=0 && d[tx][ty-1]-1==d[tx][ty]) num[tx][ty-1]+=tnum[tx][ty-1]*num[tx][ty]/t; if(ty+1 <M && d[tx][ty+1]-1==d[tx][ty]) num[tx][ty+1]+=tnum[tx][ty+1]*num[tx][ty]/t; } // qx.pop() , qy.pop(); } } }