题意:问两个迷宫是否存在公共最短路。

题解:两个反向bfs建立层次图,一遍正向bfs寻找公共最短路

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = +; int d1[maxn][maxn];
int d2[maxn][maxn]; char g1[maxn][maxn];
char g2[maxn][maxn]; int n,m;
struct node{
int x,y;
node(int X = , int Y = ){
x = X; y = Y;
}
}; int dx[] = {,-,,};
int dy[] = {,,,-};
//1,1
void rbfs(int id)
{
char (*G)[maxn];
int (*vis)[maxn];
if(id == ) G = g1, vis = d1;
else G = g2, vis = d2;
memset(vis,-,sizeof(d1));
queue<node>q;
node u(n-,m-);
q.push(u);
vis[u.x][u.y] = ;
while(q.size()){
u = q.front();q.pop();
if(u.x == && u.y == ) return;
for(int i = ; i < ; i++){
int nx = u.x + dx[i], ny = u.y + dy[i];
if(nx>=&&nx<n&&ny>=&&ny<m&&G[nx][ny]!='#'&&!~vis[nx][ny]){
vis[nx][ny] = vis[u.x][u.y]+;
q.push(node(nx,ny));
}
}
}
}
bool vis[maxn][maxn]; bool bfs()
{
if(d1[][] != d2[][] )return false;
memset(vis,,sizeof(vis));
queue<node>q;
q.push(node(,));
int tx = n-, ty = m-;
while(q.size()){
node &u = q.front();
if(u.x == tx && u.y == ty) return true;
for(int i = ; i < ; i++){
int nx = u.x + dx[i], ny = u.y + dy[i];
if(nx>=&&nx<n&&ny>=&&ny<m&&
d1[nx][ny] == d1[u.x][u.y] - && d2[nx][ny] == d2[u.x][u.y] - && !vis[nx][ny]){
vis[nx][ny] = ;
q.push(node(nx,ny));
}
}
q.pop();
}
return false;
} int main()
{
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i = ; i < n; i++)
scanf("%s",g1[i]);
for(int i = ; i < n; i++)
scanf("%s",g2[i]);
rbfs();
rbfs();
printf("%s\n",bfs()?"YES":"NO");
return ;
}

最新文章

  1. Git的四个基本概念及 git的工作流程
  2. PHP 分页函数
  3. 小结一下前段时间做的rpgdemo
  4. 在Android中调用WebService
  5. ROS多个master消息互通
  6. 一起学CUDA(一)
  7. hdu 1839 Delay Constrained Maximum Capacity Path 二分/最短路
  8. 嵌入式linux无线网卡的使用
  9. 了不起的分支和循环02 - 零基础入门学习Python008
  10. component及刚体rigidbody用法
  11. Ehcache
  12. 2018-2019-1 20189203《Linux内核原理与分析》第四周作业
  13. QT移植无法启动 This application failed to start because it could not find or load the QT platform
  14. More Effective C++ Item14:明智运用exception specifications
  15. delphi ribbon使用
  16. SharePoint 2013 How to Backup Site Collection Automatically With a PowerShell Script
  17. SpringBoot不使用模板引擎直接返回html
  18. 【转】NHibernate主键类型介绍
  19. Android内存泄漏分析实战
  20. WWDC 2014 Session笔记 - iOS界面开发的大一统

热门文章

  1. 【转】Js 数组转JSON格式
  2. floyd判环算法(龟兔赛跑算法)
  3. 洛谷P2280 [HNOI2003]激光炸弹
  4. ajax上传文件及nodeJS接收
  5. 架构sass文件
  6. this真题编译
  7. 14.插入数据、复制数据--SQL
  8. ES6新特性使用小结(三)
  9. 【BZOJ2428】均分数据
  10. POJ3178 计算几何+DP