Catch him
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 444 Accepted Submission(s): 204
Problem Description
在美式足球中，四分衛負責指揮整只球隊的進攻戰術和跑位，以及給接球員傳球的任務。四分衛是一只球隊進攻組最重要的球員，而且一般身體都相對比較弱小，所以通常球隊會安排5-7名大漢來保護他，其中站在四分衛前方、排成一線的5名球員稱為進攻鋒線，他們通常都是135公斤左右的壯漢。
對防守方來說，攻擊對手的四分衛當然是最直接的限制對手進攻的方法。如果效果好，就可以在對方四分衛傳球之前將其按翻在地，稱之為擒殺。擒殺是最好的鼓舞防守隊士氣的方法，因為對方連傳球的機會都沒有，進攻就結束了，還必須倒退一些距離開球。凶狠的擒殺甚至能夠將對方的四分衛弄傷，從而迫使對方更換這個進攻核心。
在本題中，輸入給出准備擒殺四分衛的防守球員的位置、對方每個進攻鋒線球員的位置以及對方四分衛的位置，你的任務是求出這名准備擒殺的防守球員至少要移動多少步，才能夠擒殺對方四分衛。
假設對方進攻鋒線和四分衛在這個過程中都不會移動。只有1名防守球員，防守球員只要碰到對方四分衛就算擒殺。
所有的球員都是一塊連續的、不中空的2維區域。防守球員不可以從進攻鋒線的身體上穿過，也不可以從界外穿過(只能走空地)。
防守隊員不可以轉動身體，只能平移。防守隊員的身體所有部分向同一個方向(上、下、左、右)移動1格的過程叫做1步。
Input
輸入包含多組數據。每組數據第一行都是兩個整數H，W(0<H,W<=100)，表示整個區域的高度和寬度，H=W=0表示輸入結束。接下來有H行，每行W個字符。每個字符如果是’.’，表示這裡是空地，如果是’O’，表示是進攻鋒線隊員的身體，如果是’D’，表示是准備擒殺的防守球員的身體，如果是’Q’，表示是四分衛的身體。
輸入保證符合上面的條件。防守球員的身體總共不超過20格。
Output
對每組數據，輸出包含擒殺所需最少步數的一行。如果不能擒殺，輸出帶’Impossible’的一行。
Sample Input
6 6
.Q....
QQ..OO
.OO..O
...O.O
OO.O..
....DD
7 7
.Q.....
QQ.OOO.
...O...
O......
OO..OO.
.O.....
.....DD
0 0
Sample Output
Impossible
9
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=100+10;
char Map[MAX][MAX];
int mark[MAX][MAX];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int n,m,size;
struct Node{
int x[21],y[21],time,A,B;
Node(){}
Node(int X,int Y,int i){
x[i]=X;
y[i]=Y;
}
}start;
int BFS(int &flag){
int j;
queue<Node>q;
Node oq,next;
q.push(start);
mark[start.x[0]][start.y[0]]=flag;
while(!q.empty()){
oq=q.front();
q.pop();
for(int i=0;i<4;++i){
for(j=0;j<size;++j){
next=Node(oq.x[j]+dir[i][0],oq.y[j]+dir[i][1],j);
if(next.x[j]<0 || next.y[j]<0 || next.x[j]>=n || next.y[j]>=m)break;
if(Map[next.x[j]][next.y[j]] == 'O')break;
}
if(j != size)continue;
if(mark[next.x[0]][next.y[0]] == flag)continue;
next.time=oq.time+1;
mark[next.x[0]][next.y[0]]=flag;
for(j=0;j<size;++j)
if(Map[next.x[j]][next.y[j]] == 'Q')return next.time;
q.push(next);
}
}
return -1;
}
int main(){
int num=0;
while(cin>>n>>m,n+m){
size=0;
for(int i=0;i<n;++i)cin>>Map[i];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(Map[i][j] == 'D'){
start.x[size]=i;
start.y[size++]=j;
}
}
}
start.time=0;
int temp=BFS(++num);
if(temp == -1)cout<<"Impossible"<<endl;
else cout<<temp<<endl;
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=100+10;
char Map[MAX][MAX];
int mark[MAX][MAX];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int n,m,size;
struct Node{
int x[21],y[21],time,A,B;
Node(){}
Node(int X,int Y,int i){
x[i]=X;
y[i]=Y;
}
}start;
int BFS(int &flag){
int j;
queue<Node>q;
Node oq,next;
q.push(start);
mark[start.x[0]][start.y[0]]=flag;
while(!q.empty()){
oq=q.front();
q.pop();
for(int i=0;i<4;++i){
for(j=0;j<size;++j){
next=Node(oq.x[j]+dir[i][0],oq.y[j]+dir[i][1],j);
if(next.x[j]<0 || next.y[j]<0 || next.x[j]>=n || next.y[j]>=m)break;
if(Map[next.x[j]][next.y[j]] == 'O')break;
}
if(j != size)continue;
if(mark[next.x[0]][next.y[0]] == flag)continue;
next.time=oq.time+1;
mark[next.x[0]][next.y[0]]=flag;
for(j=0;j<size;++j)
if(Map[next.x[j]][next.y[j]] == 'Q')return next.time;
q.push(next);
}
}
return -1;
}
int main(){
int num=0;
while(cin>>n>>m,n+m){
size=0;
for(int i=0;i<n;++i)cin>>Map[i];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(Map[i][j] == 'D'){
start.x[size]=i;
start.y[size++]=j;
}
}
}
start.time=0;
int temp=BFS(++num);
if(temp == -1)cout<<"Impossible"<<endl;
else cout<<temp<<endl;
}
return 0;
}
