这题坑了我好久，还是那句话只要你真心去做一定能想出办法来。这题办法倒是想出来了，但是我标记的是身体的全部，每次都这样，只有检测到全部被标记时才不继续往下搜索，测试数据试很多也没找出错误来，最后才知道只要标记一个就行，而且必须一直标记同一个。。
代码：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std ;
int r ;
int n,m ;
int vx[105],vy[105] ;
char s[105][105] ;
int vis[105][105] ;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
struct zhang
{
int x[25],y[25],bu ;
} ;
int bfs()
{
queue<zhang>q ;
zhang current,next ;
int i,j,k ;
int nx,ny ;
for(i=0;i<r;i++)
{
current.x[i]=vx[i] ;
current.y[i]=vy[i] ;
}
vis[current.x[0]][current.y[0]]=1 ;//每次标记开始那一点
current.bu=0 ;
q.push(current) ;
while(!q.empty())
{
current=q.front() ;
q.pop() ;
for(i=0;i<4;i++)
{
int p=0,ret=0 ;
for(j=0;j<r;j++)
{
next.x[j]=current.x[j]+dx[i] ;
next.y[j]=current.y[j]+dy[i] ;
nx=next.x[j] ;
ny=next.y[j] ;
if(!j&&vis[nx][ny])
ret=1 ;
if(nx<0||nx>=n||ny<0||ny>=m||s[nx][ny]=='O')
{
ret=1 ;
break ;
}
if(s[nx][ny]=='Q')
p=1 ;
}
if(ret)
continue ;
if(p)
return current.bu+1 ;
for(k=0;k<r;k++)
{
next.x[k]=current.x[k]+dx[i] ;
next.y[k]=current.y[k]+dy[i] ;
nx=next.x[k] ;
ny=next.y[k] ;
if(!k)
vis[nx][ny]=1 ;
}
next.bu=current.bu+1 ;
q.push(next) ;
}
}
return -1 ;
}
int main()
{
int i,j ;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m)
break ;
r=0 ;
memset(vis,0,sizeof(vis)) ;
for(i=0;i<n;i++)
{
scanf("%s",s[i]) ;
for(j=0;j<m;j++)
if(s[i][j]=='D')
{
vx[r]=i ;
vy[r]=j ;
r++ ;
}
}
int mx=bfs() ;
if(mx==-1)
printf("Impossible\n") ;
else printf("%d\n",mx) ;
}
return 0 ;
}