题目传送门

 /*
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 ;
}

最新文章

  1. python Requests库在处理response时的一些陷阱
  2. CSS强制性换行word-break与word-wrap的使用
  3. [DE2i-150] 重建PCIe_Fundmental範例說明
  4. WINCE6.0组件选择说明
  5. jQuery 遍历each()的使用方法
  6. C# List 用法与示例
  7. ASP.NET 优化 check list
  8. 0.0C语言重点问题回顾
  9. C++的学习记录 - 0
  10. jQuery 局部div刷新和全局刷新方法
  11. PowerDesigner使用方法小结
  12. Java性能优化_转载
  13. Linux 内核配置机制(make menuconfig、Kconfig、makefile)讲解
  14. window server 2008 安装Oracle10g
  15. go使用rpc
  16. JavaScript黑客是这样窃取比特币的,Vue开发者不用担心!
  17. 软件工程 week 02
  18. C_数据结构_递归不同函数间调用
  19. Vue -- vue-cli webpack打包开启Gzip 报错
  20. 光荣之路测试开发面试linux考题之四:性能命令

热门文章

  1. BZOJ2272: [Usaco2011 Feb]Cowlphabet 奶牛文字
  2. POJ 3415 (后缀自动机)
  3. Thinkphp5.0 的使用模型Model添加数据
  4. 基于端口的信息探测-portscan-1.0
  5. JavaScript面向对象实现
  6. [bzoj2453]维护队列_带修改莫队
  7. [bzoj3630][JLOI2014]镜面通道_计算几何_网络流_最小割
  8. Codeforces Educational Round 21
  9. MongoDB小结18 - find【查询条件$not】
  10. jmeter的dubbo压测,依赖jar包要放到执行机的lib/ext下