﻿HDU 2531 Catch him(块状BFS)-Ocrosoft

Catch him

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 857    Accepted Submission(s): 400

Problem Description

Input

Output

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

```

Solution

```#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
template <typename T>
{
cin>>t;
return t;
}
int n,m;
char mp[101][101];
bool vis[101][101];//vis记录主节点的位置即可
struct D//防守队员
{
D(){cnt=0,ms(x),ms(y),step=0;}
void ini(){cnt=0,ms(x),ms(y),step=0;}
void update(int xi,int yi)//更新身体位置
{
hx+=xi,hy+=yi,step++;
}
bool check()//检查是否能够移动
{
if(hx<0||hx>=n||hy<0||hy>=m)return 0;
for(int i=0; i<cnt; i++)
if(hx+x[i]<0||hx+x[i]>=n||hy+y[i]<0||hy+y[i]>=m)return 0;
if(vis[hx][hy])return 0;
if(mp[hx][hy]=='O')return 0;
for(int i=0; i<cnt; i++)
if(mp[hx+x[i]][hy+y[i]]=='O')return 0;
return 1;
}
bool judge()//判断是否成功
{
if(mp[hx][hy]=='Q')return 1;
for(int i=0; i<cnt; i++)
if(mp[hx+x[i]][hy+y[i]]=='Q')return 1;
return 0;
}
int hx,hy;//主节点
int cnt,step;//其他节点的个数
int x[21],y[21];//其他节点对于主节点的相对位置
} d,t;
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
int bfs()
{
ms(vis);
queue<D> q;
vis[d.hx][d.hy]=1;
q.push(d);
while(!q.empty())
{
d=q.front(),q.pop();
if(d.judge())return d.step;
for(int i=0; i<4; i++)
{
t=d,t.update(dir[i][0],dir[i][1]);
if(!t.check())continue;//越界、遇到壮♂汉、访问过
vis[t.hx][t.hy]=1;
q.push(t);
}
}
return -1;
}
int main()
{
while(cin>>n>>m&&(n||m))
{
d.ini();
for(int i=0; i<n; i++)cin>>mp[i];
for(int i=0,flag=1; i<n; i++)
for(int j=0; j<m; j++)
if(mp[i][j]=='D')
{
if(flag)d.hx=i,d.hy=j,flag=0;
else d.x[d.cnt]=i-d.hx,d.y[d.cnt++]=j-d.hy;
}
int ans=bfs();
if(ans==-1)printf("Impossible\n");
else printf("%d\n",ans);
}
return 0;
}
```