注意：先处理出起点的整个body，并存储在form中，然后再建个新的图flag，再就是普通的bfs了。。。。。
参考：http://blog.csdn.net/ice_crazy/article/details/7594362
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 = 105; 8 const int maxm = 2005; 9 const int inf = 999999; 10 const int dx[]={0,0,1,-1}; 11 const int dy[]={1,-1,0,0}; 12 char mat[ maxn ][ maxn ]; 13 int mp[ maxn ][ maxn ];//对应着mat 14 int flag[ maxn ][ maxn ];//bf时候，存储着mat中的点能否走，1 is ok 15 int form[ maxn ][ maxn ];//存储着运动员的身体，0：不是身体的一部分，1：是身体的一部分 16 int vis[ maxn ][ maxn ]; 17 int n,m; 18 int up,left,down,right; 19 struct node{ 20 int x,y,t; 21 }pp,p; 22 queue<node>q; 23 24 void init(){ 25 //memset( flag,0,sizeof( flag )); 26 //memset( form,0,sizeof( form )); 27 up=inf; 28 left=inf; 29 right=-1; 30 down=-1; 31 } 32 33 int bfs(){ 34 memset( vis,0,sizeof( vis )); 35 while( !q.empty() ) q.pop(); 36 p.x=up,p.y=left,p.t=0; 37 q.push( p ); 38 vis[ p.x ][ p.y ]=1; 39 while( !q.empty() ){ 40 p=q.front(),q.pop(); 41 for( int i=0;i<(down-up+1);i++ ){ 42 for( int j=0;j<(right-left+1);j++ ){ 43 if( form[i][j]==1&&mp[i+p.x][j+p.y]==3 ){ 44 return p.t; 45 } 46 } 47 } 48 for( int k=0;k<4;k++ ){ 49 pp.x=p.x+dx[ k ],pp.y=p.y+dy[ k ],pp.t=p.t+1; 50 if( pp.x<0||pp.x>=n||pp.y<0||pp.y>=m ) continue; 51 if( flag[ pp.x ][ pp.y ]==0 ) continue; 52 if( vis[ pp.x ][ pp.y ]==1 ) continue; 53 vis[ pp.x ][ pp.y ]=1; 54 q.push( pp ); 55 } 56 } 57 return -1; 58 } 59 60 int main(){ 61 while( scanf("%d%d",&n,&m)==2,n+m ){ 62 init(); 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]=='.' ) mp[i][j]=1;//ok 67 else if( mat[i][j]=='O') mp[i][j]=-1;//no 68 else if( mat[i][j]=='D' ) mp[i][j]=2;//body 69 else if( mat[i][j]=='Q' ) mp[i][j]=3;//目标 70 if( mp[i][j]==2 ){ 71 if( up>i ) up=i; 72 if( down<i ) down=i; 73 if( left>j ) left=j; 74 if( right<j ) right=j; 75 } 76 } 77 } 78 int i1,i2,j1,j2; 79 for( i1=up,i2=0;i2<(down-up+1);i1++,i2++ ){ 80 for( j1=left,j2=0;j2<(right-left+1);j1++,j2++ ){ 81 if( mp[i1][j1]==2 ){ 82 form[i2][j2]=1; 83 mp[i1][j1]=1; 84 } 85 else{ 86 form[i2][j2]=0; 87 } 88 } 89 }//整理出起点的body 90 int f; 91 for( i1=0;i1<n;i1++ ){ 92 for( j1=0;j1<m;j1++ ){ 93 f=1; 94 for( i2=0;i2<down-up+1;i2++ ){ 95 for( j2=0;j2<right-left+1;j2++ ){ 96 if( form[i2][j2]==0 ) continue; 97 int tmp1=i1+i2; 98 int tmp2=j1+j2; 99 if( tmp1<0||tmp1>=n||tmp2<0||tmp2>=m ){ 100 f=-1; 101 break; 102 } 103 if( mp[ tmp1 ][ tmp2 ]==-1 ){ 104 f=-1; 105 break; 106 } 107 } 108 if( f==-1 ) 109 break; 110 } 111 if( f==-1 ) 112 flag[i1][j1]=0; 113 else 114 flag[i1][j1]=1; 115 } 116 }//处理出flag，在bfs中可以按照普通的求两点间距离 117 118 int ans=bfs(); 119 if( ans==-1 ) 120 printf("Impossible\n"); 121 else 122 printf("%d\n",ans); 123 } 124 return 0; 125 }