题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2531

题解 :这个题目的坑就是D的个数,一开始天真的一位就2个,不是这样的,D的数目是不定的。所以我们先找到一个D,让这个D做为头,然后再用一个数组记录其他D与该D的相对位置就好了,然后再BFS判断

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+;
char arr[N][N];
int s1,e1,s2,e2;
int n,m;
int xx,yy;
int mark[N][N];
int bodyx[N];
int bodyy[N];
int pos;
int d[][]={,,,,-,,,-};
struct stu{
int a,b;
int sum;
};
int ans;
bool judge(int x,int y){
if(mark[x][y]) return ;
if(x<||y<||x>=n||y>=m) return ;
if(arr[x][y]=='O') return ;
for(int i=;i<pos;i++){
int dx=bodyx[i]+x;
int dy=bodyy[i]+y;
if(dx<||dy<||dx>=n||dy>=m||dx<||dy<||arr[dx][dy]=='O') return ;
}
return ;
} bool juju(int x,int y){
if(arr[x][y]=='Q') return ;
for(int i=;i<pos;i++){
int dx=x+bodyx[i];
int dy=y+bodyy[i];
if(arr[dx][dy]=='Q') return ;
}
return ;
}
void bfs(int x1,int y){
queue<stu>que;
que.push({x1,y,});
mark[x1][y]=;
while(que.size()){
stu x=que.front();
que.pop();
if(juju(x.a,x.b)){
ans=x.sum;
break;
}
for(int i=;i<;i++){
int dx=x.a+d[i][];
int dy=x.b+d[i][];
if(judge(dx,dy)){
que.push({dx,dy,x.sum+});
mark[dx][dy]=;
}
}
}
}
int main(){
while(cin>>n>>m){
if(n==||m==) break;
memset(mark,,sizeof(mark));
s1=-;
ans=-;
pos=;
for(int i=;i<n;i++) scanf("%s",arr[i]);
for(int i=;i<n;i++){
for(int j=;j<m;j++){
if(arr[i][j]=='D'&&s1!=-){
bodyx[pos]=i;
bodyy[pos++]=j;
}
else if(arr[i][j]=='D'){
s1=i,e1=j;
}
}
}
for(int i=;i<pos;i++){
bodyx[i]=bodyx[i]-s1;
bodyy[i]=bodyy[i]-e1;
}
bfs(s1,e1);
if(ans!=-) cout<<ans<<endl;
else cout<<"Impossible"<<endl;
}
return ;
}

最新文章

  1. 《连载 | 物联网框架ServerSuperIO教程》-4.如开发一套设备驱动,同时支持串口和网络通讯。附:将来支持Windows 10 IOT
  2. 【C#进阶系列】16 数组
  3. js实现自定义右键菜单--兼容IE、Firefox、Chrome
  4. 数据库中User和Schema的关系
  5. Tornado web.authenticated 用户认证浅析
  6. GWT环境搭建--eclipse
  7. java中Integer包装类的具体解说(java二进制操作,全部进制转换)
  8. C#跨窗体调用控件(委托回调函数使用例子)
  9. ios自定义UIButton内部空间Rect
  10. 基于oracle的sql优化
  11. c语言变量类型联想
  12. cnblog测试
  13. 实例详解:MFC坐标轴实现
  14. npm WARN react-native-maps@0.14.0 requires a peer of react@&gt;=15.4.0 but none was installed
  15. VS2013+opencv2.4.9配置
  16. 面向对象SOLID设计原则之Open-Closed原则
  17. Gradle Goodness: Copy Files with Filtering
  18. django from组件 实现增加 删除 编辑(推荐用法)
  19. Service的用法
  20. shodan在渗透测试中的应用

热门文章

  1. effective-java学习笔记---使用枚举类型替代整型常量34
  2. PyTorch专栏(六): 混合前端的seq2seq模型部署
  3. TensorFlow系列专题(三):深度学习简介
  4. Dropout的前世与今生
  5. C 2010年笔试题
  6. flask操作数据库 以及 建表
  7. CVE-2020-7961 Liferay Portal 复现分析
  8. 字符串学习笔记(二)---- StringBuffer
  9. PTA | 1029 旧键盘 (20分)
  10. .Net微服务实践(五)[服务发现]:Consul介绍和环境搭建