CF Gym 100187E Two Labyrinths (迷宫问题)
2024-08-27 02:01:03
题意:问两个迷宫是否存在公共最短路。
题解:两个反向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 ;
}
最新文章
- Git的四个基本概念及 git的工作流程
- PHP 分页函数
- 小结一下前段时间做的rpgdemo
- 在Android中调用WebService
- ROS多个master消息互通
- 一起学CUDA(一)
- hdu 1839 Delay Constrained Maximum Capacity Path 二分/最短路
- 嵌入式linux无线网卡的使用
- 了不起的分支和循环02 - 零基础入门学习Python008
- component及刚体rigidbody用法
- Ehcache
- 2018-2019-1 20189203《Linux内核原理与分析》第四周作业
- QT移植无法启动 This application failed to start because it could not find or load the QT platform
- More Effective C++ Item14:明智运用exception specifications
- delphi ribbon使用
- SharePoint 2013 How to Backup Site Collection Automatically With a PowerShell Script
- SpringBoot不使用模板引擎直接返回html
- 【转】NHibernate主键类型介绍
- Android内存泄漏分析实战
- WWDC 2014 Session笔记 - iOS界面开发的大一统