【Gym 100971J】Robots at Warehouse
2024-08-25 22:33:52
题意
链接
给你一个n*m的地图,'#'代表墙,‘.’代表可走的,1代表1号机器人,2代表2号机器人,机器人可以上下左右移动到非墙的位置,但不能走到另一个机器人身上。问能否交换1和2的位置。
分析
如果1和2之间有路径且路径上某个点的度大于2,那就是YES,如果1和2的路径构成一个回路也是YES。其他情况就是NO。
代码
#include<cstdio>
#define N 200005
int n,m,ux,uy,ax,ay,a[N],u[N],ck,ans,fx[]= {,-,,},fy[]= {,,,-};
char c;
bool circle;
void dfs(int x,int y,int s){
if(x==ax&&y==ay)//走到终点
ans++;
if(x==ux&&y==uy&&s>)//走回起点(s是第几步)
circle = true;
if(u[x*m-m+y]||ans>||ans&&ck)return;
u[x*m-m+y]=;
int r=;
for(int i=;i<;i++){
int nx=x+fx[i];
int ny=y+fy[i];
if(nx&&nx<=n&&ny&&ny<=m&&a[nx*m-m+ny]){
r++;//点的度
if(r>)ck=;
dfs(nx,ny,s+);
}
}
}
int main(){
scanf("%d%d ",&n,&m);
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
c=getchar();
if(c!='#')
a[i*m-m+j]=;
if(c=='')
{
ux=i;
uy=j;
}
else if(c=='')
{
ax=i;
ay=j;
}
}
getchar();
}
dfs(ux,uy,);
if(ans&&(ck||circle))printf("YES");
else printf("NO");
return ;
}
最新文章
- Python 爬虫4——使用正则表达式筛选内容
- Weblogic的安装与配置
- Android4.4 往短信收件箱中插入自定义短信(伪造短信)
- Oracle 11g 下载|Oracle 11g 官网下载|Oracle 11g 官网下载 带登录用户和密码
- Wysiwyg Editors 标签过滤
- linux 如何开机自动运行sh脚本
- Thrift 个人实战--Thrift 的序列化机制
- canvas应用-思维导图
- 腾讯sdk学到了
- SQL Server 收缩事务日志的方法
- 单链表反转的递归实现(Reversing a Linked List in Java, recursively)
- iOS 中的正则匹配(工具类方法)
- H5_background-clip(css3——裁剪)
- Prism for Xamarin.Forms
- c++(八皇后)
- 亲戚(relative)
- DBCP 连接池
- vs code 操作Git
- python各种类型日期转换大全
- [CF453B]Little Pony and Harmony Chest