Catch him（HDU-2351）
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
思路：
? ? 與一般的bfs題不同，本題是以“塊”為單位（即：身體體積），來進行移動和判斷操作。
? ? 所以開的結構體是“塊”（數組），用每一個點的集合來表示。
Source Program
#include<cstring> #include<cstdio> #include<queue> using namespace std;char mapp[105][105]; int vis[105][105]; int h,w; int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};struct body{ int x[25]; int y[25]; int k; int step; }start,now,nextt;void bfs() {queue<body> q;int i,j;int x,y;bool flag;vis[start.x[0]][start.y[0]]=1;memset(vis,0,sizeof(vis));q.push(start);//元素入隊while(!q.empty()){now=q.front();q.pop();//出隊for(i=0;i<now.k;i++){if(mapp[now.x[i]][now.y[i]]=='Q')//成功撲殺，輸出最小步數{printf("%d\n",now.step);return;}}for(i=0;i<4;i++){flag=true;for(j=0;j<now.k;j++){x=nextt.x[j]=now.x[j]+direction[i][0];y=nextt.y[j]=now.y[j]+direction[i][1];nextt.step=now.step+1;//統計步數nextt.k=now.k;//記錄位置if(vis[nextt.x[0]][nextt.y[0]]){flag=false;break;}if(nextt.x[j]<0||nextt.x[j]>=h||nextt.y[j]<0||nextt.y[j]>=w||mapp[nextt.x[j]][nextt.y[j]]=='O'){flag=false;break;} //越界判斷}if(flag)//子節點滿足條件{q.push(nextt);//入列vis[nextt.x[0]][nextt.y[0]]=1;}}}printf("Impossible\n"); }int main() {int i,j;int k;while(scanf("%d %d",&h,&w)!=EOF){if(h==0&&w==0) break;k=0;for(i=0;i<h;i++){scanf("%s",mapp[i]);//以字符串的形式輸入for(j=0;j<w;j++){if(mapp[i][j]=='D') //記錄擒殺隊員位置{start.x[k]=i;start.y[k]=j;k++;}}}start.k=k;//記錄初始位置start.step=0;//記錄初始步數bfs();}return 0; }?
總結
以上是生活随笔為你收集整理的Catch him（HDU-2351）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 信息学奥赛一本通C++语言——1124：
- 下一篇： 有一门课不及格的学生（信息学奥赛一本通-