BFS HDOJ 1728 逃离迷宫
2024-08-30 19:40:53
/*
BFS:三维BFS,加上方向。用dp[x][y][d]记录当前需要的最少转向数
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std; const int MAXN = 1e2 + ;
const int INF = 0x3f3f3f3f;
struct P
{
int x, y, z;
}now, to;
char maze[MAXN][MAXN];
int dp[MAXN][MAXN][];
bool inq[MAXN][MAXN][];
int dx[] = {-, , , };
int dy[] = {, , -, };
int k, x1, y1, x2, y2;
int n, m; bool check(int x, int y)
{
if (x >= && x <= n && y >= && y <= m) return true;
else return false;
} bool BFS(void)
{
memset (dp, , sizeof (dp));
memset (inq, false, sizeof (inq));
queue<P> Q;
for (int i=; i<=n; ++i)
{
for (int j=; j<=m; ++j)
{
for (int l=; l<; ++l)
{
dp[i][j][l] = INF; inq[i][j][l] = false;
}
}
}
for (int i=; i<; ++i)
{
dp[x1][y1][i] = ; inq[x1][y1][i] = true;
Q.push ((P) {x1, y1, i});
} while (!Q.empty ())
{
now = Q.front (); Q.pop ();
for (int i=; i<; ++i)
{
to.x = now.x + dx[i];
to.y = now.y + dy[i]; to.z = i;
if (check (to.x, to.y) && maze[to.x][to.y] == '.')
{
int tmp = dp[now.x][now.y][now.z];
if (to.z == now.z)
{
if (tmp < dp[to.x][to.y][to.z])
{
dp[to.x][to.y][to.z] = tmp;
if (!inq[to.x][to.y][to.z])
{
inq[to.x][to.y][to.z] = true; Q.push (to);
}
}
}
else
{
if (++tmp < dp[to.x][to.y][to.z])
{
dp[to.x][to.y][to.z] = tmp;
if (!inq[to.x][to.y][to.z])
{
inq[to.x][to.y][to.z] = true; Q.push (to);
}
}
}
}
}
inq[now.x][now.y][now.z] = false;
} for (int i=; i<; ++i)
{
if (dp[x2][y2][i] <= k) return true;
} return false;
} int main(void) //HDOJ 1728 逃离迷宫
{
// freopen ("HDOJ_1728.in", "r", stdin); int t; scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &m);
for (int i=; i<=n; ++i) scanf ("%s", maze[i] + );
scanf ("%d%d%d%d%d", &k, &y1, &x1, &y2, &x2);
if (BFS ()) puts ("yes");
else puts ("no");
} return ;
}
最新文章
- python Requests库在处理response时的一些陷阱
- CSS强制性换行word-break与word-wrap的使用
- [DE2i-150] 重建PCIe_Fundmental範例說明
- WINCE6.0组件选择说明
- jQuery 遍历each()的使用方法
- C# List 用法与示例
- ASP.NET 优化 check list
- 0.0C语言重点问题回顾
- C++的学习记录 - 0
- jQuery 局部div刷新和全局刷新方法
- PowerDesigner使用方法小结
- Java性能优化_转载
- Linux 内核配置机制(make menuconfig、Kconfig、makefile)讲解
- window server 2008 安装Oracle10g
- go使用rpc
- JavaScript黑客是这样窃取比特币的,Vue开发者不用担心!
- 软件工程 week 02
- C_数据结构_递归不同函数间调用
- Vue -- vue-cli webpack打包开启Gzip 报错
- 光荣之路测试开发面试linux考题之四:性能命令
热门文章
- BZOJ2272: [Usaco2011 Feb]Cowlphabet 奶牛文字
- POJ 3415 (后缀自动机)
- Thinkphp5.0 的使用模型Model添加数据
- 基于端口的信息探测-portscan-1.0
- JavaScript面向对象实现
- [bzoj2453]维护队列_带修改莫队
- [bzoj3630][JLOI2014]镜面通道_计算几何_网络流_最小割
- Codeforces Educational Round 21
- MongoDB小结18 - find【查询条件$not】
- jmeter的dubbo压测,依赖jar包要放到执行机的lib/ext下