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