题意

链接
给你一个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 ;
}

最新文章

  1. Python 爬虫4——使用正则表达式筛选内容
  2. Weblogic的安装与配置
  3. Android4.4 往短信收件箱中插入自定义短信(伪造短信)
  4. Oracle 11g 下载|Oracle 11g 官网下载|Oracle 11g 官网下载 带登录用户和密码
  5. Wysiwyg Editors 标签过滤
  6. linux 如何开机自动运行sh脚本
  7. Thrift 个人实战--Thrift 的序列化机制
  8. canvas应用-思维导图
  9. 腾讯sdk学到了
  10. SQL Server 收缩事务日志的方法
  11. 单链表反转的递归实现(Reversing a Linked List in Java, recursively)
  12. iOS 中的正则匹配(工具类方法)
  13. H5_background-clip(css3——裁剪)
  14. Prism for Xamarin.Forms
  15. c++(八皇后)
  16. 亲戚(relative)
  17. DBCP 连接池
  18. vs code 操作Git
  19. python各种类型日期转换大全
  20. [CF453B]Little Pony and Harmony Chest

热门文章

  1. hdu-5521 Meeting(最短路)
  2. Sql助手
  3. Android Studio系列教程四--Gradle基础
  4. 【转】【PNG压缩工具】PNG 图像的优化及压缩工具介绍
  5. drbd初探及Heartbeat+DRBD+MySQL
  6. R树空间索引
  7. C# 利用QRCode生成二维码图片
  8. 联想Y50p预装win8系统改为win7
  9. ubuntu上怎么设置默认python命令是执行python3而不是python2
  10. 北京联想招聘-Android高级工程师(5-7年) 加入qq 群:220486180 或者直接在此 留言咨询