题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2531
题目大意： 你的身体占据多个点。每次移动全部的点，不能撞到障碍点，问撞到目标点块（多个点）的最少步数。
解题思路：
挺有趣的一个题，每次要移动多个点。
如果只移动一个点，就是个简单粗暴的BFS。
多个点照样处理，读图的时候把扫到的第一个点当作移动点，然后vector记录下身体的其它点与该移动点的相对坐标。
BFS的时候，先看看移动点能不能动，然后再根据身体的相对坐标还原出身体的绝对坐标，看看有没有越界或是撞到障碍。
顺便检测一下是否撞到目标点。
#include "cstdio"
#include "iostream"
#include "cstring"
#include "queue"
#include "string"
#include "vector"
using namespace std;
struct status
{
int x,y,dep;
status(int x,int y,int dep):x(x),y(y),dep(dep) {}
};
char map[][];
int n,m,sx,sy,vis[][],dir[][]={-,,,,,-,,},ans;
vector<status> body;
void bfs(int sx,int sy)
{
queue<status> Q;
Q.push(status(sx,sy,));
vis[sx][sy]=true;
bool flag=false;
while(!Q.empty())
{
if(flag) break;
status t=Q.front();Q.pop();
//cout<<map[t.x][t.y]<<endl;
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][];
if(vis[X][Y]||X<||X>n||Y<||Y>m||map[X][Y]=='O') continue;
bool ok=true,get=false;
for(int k=;k<body.size();k++)
{
int bx=X-body[k].x,by=Y-body[k].y;
if(bx<||bx>n||by<||by>m||map[bx][by]=='O') {ok=false;break;}
if(map[bx][by]=='Q') get=true;
}
if(!ok) continue;
vis[X][Y]=true;
if(get||map[X][Y]=='Q') {flag=true;ans=min(ans,t.dep+);break;}
Q.push(status(X,Y,t.dep+));
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
string tt;
while(cin>>n>>m&&n)
{
body.clear();
memset(vis,,sizeof(vis));
bool first=false;ans=<<;
for(int i=;i<=n;i++)
{
cin>>tt;
for(int j=;j<tt.size();j++)
{
map[i][j+]=tt[j];
if(tt[j]=='D')
{
if(!first) {sx=i;sy=j+;first=true;}
else {body.push_back(status(sx-i,sy-(j+),));}
}
}
}
bfs(sx,sy);
if(ans==<<) cout<<"Impossible"<<endl;
else cout<<ans<<endl;
}
}
| 11882814 | 2014-10-16 01:36:06 | Accepted | 2531 | 15MS | 352K | 1971 B | C++ | Physcal |