题意：从起点到终点
bfs即可
注意P的作用：一遇到P即将所有的P进队。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 const int maxn = 5005; 8 const int inf=999999; 9 char mat[ maxn ][ maxn ]; 10 bool vis[ maxn ][ maxn ]; 11 struct node{ 12 int x,y,s; 13 }p,pp,tmp; 14 struct node2{ 15 int x,y; 16 }sump[ maxn ],mystart,myend; 17 int n,m,cost; 18 int ans; 19 int cnt;//the sum of the "p" 20 const int dx[]={0,0,1,-1}; 21 const int dy[]={1,-1,0,0}; 22 23 void bfs( ){ 24 p.x=mystart.x,p.y=mystart.y,p.s=0; 25 memset( vis,0,sizeof( vis ) ); 26 vis[ p.x ][ p.y ]=1; 27 queue<node>q; 28 q.push( p ); 29 int temp_flag=-1;//用于统计"P"是否进队 30 while( !q.empty() ){ 31 p=q.front(),q.pop(); 32 //printf("p.x:%d p.y:%d p.t:%d \n",p.x,p.y,p.s); 33 //if( p.x==myend.x && p.y==myend.y ) ans=min( ans,p.s ); 34 for( int i=0;i<4;i++ ){ 35 pp.x=p.x+dx[ i ],pp.y=p.y+dy[ i ],pp.s=p.s; 36 if( pp.x<0||pp.x>=n||pp.y<0||pp.y>=m ) continue; 37 if( vis[ pp.x ][ pp.y ]==1 ||mat[ pp.x ][ pp.y ]=='#' ) continue; 38 if( mat[ pp.x ][ pp.y ]=='*' ){ 39 vis[ pp.x ][ pp.y ]=1; 40 pp.s=p.s+cost; 41 q.push( pp ); 42 } 43 else if( mat[ pp.x ][ pp.y ]=='P' && temp_flag==-1 ){ 44 temp_flag=1; 45 for( int k=0;k<cnt;k++ ){ 46 tmp.x=sump[k].x,tmp.y=sump[k].y,tmp.s=pp.s; 47 vis[ tmp.x ][ tmp.y ]=1; 48 q.push( tmp ); 49 } 50 } 51 else if( mat[ pp.x ][ pp.y ]=='C' ){ 52 ans=min( ans,pp.s ); 53 return ; 54 } 55 } 56 } 57 //return ans; 58 } 59 60 int main(){ 61 while( scanf("%d%d%d",&n,&m,&cost)!=EOF ){ 62 cnt=0; 63 for( int i=0;i<n;i++ ){ 64 scanf("%s",mat[ i ]); 65 for( int j=0;j<m;j++ ){ 66 if( mat[ i ][ j ]=='Y' ) mystart.x=i,mystart.y=j; 67 else if( mat[ i ][ j ]=='C' ) myend.x=i,myend.y=j; 68 else if( mat[ i ][ j ]=='P' ){ 69 sump[ cnt ].x=i; 70 sump[ cnt ].y=j; 71 cnt++; 72 } 73 } 74 } 75 //printf("cnt:%d\n",cnt); 76 ans=inf; 77 bfs(); 78 if( ans==inf ) printf("Damn teoy!\n"); 79 else printf("%d\n",ans); 80 } 81 return 0; 82 }