题目链接

给一个迷宫,问从起点到终点存不存在一条长度为T的路径。

-----------------------------------------------------------------------------

判断(T-当前步数)的奇偶性 和 (终点-当前位置)距离的奇偶性是否相同。

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
typedef long long LL;
using namespace std;
const int N = ;
const int skip[][] = { { , }, { -, }, { , }, { , - } }; int m, n, t;
int sx, sy, ex, ey;
char maze[N][N];
bool vis[N][N];
bool judge(int x, int y){
if (x< || y< || x >= m || y >= n) return false;
if (vis[x][y]) return false;
if (maze[x][y] == 'X') return false;
return true;
} bool dfs(int x, int y, int step){
if (x == ex&&y == ey&&step == t) return true;
int tag = t - step - abs(ex-x) - abs(ey-y);
if(tag<||tag&) return false;
for (int i = ; i<; i++){
int tx = x + skip[i][];
int ty = y + skip[i][];
if (judge(tx, ty)){
vis[tx][ty] = true;
if (dfs(tx, ty, step + )) return true;
vis[tx][ty] = false;
}
}
return false;
} int main(){
while (scanf("%d%d%d", &m, &n, &t), m + n + t){
for (int i = ; i<m; i++) {
scanf("%s", maze[i]);
for (int j = ; j<n; j++){
if (maze[i][j] == 'D') sx = i, sy = j;
if (maze[i][j] == 'S') ex = i, ey = j;
}
}
memset(vis, false, sizeof(vis)); if (dfs(sx,sy,)) puts("YES");
else puts("NO");
}
return ;
}

最新文章

  1. 极光推送-适配 iOS10
  2. [置顶] 关于产品的一些思考——腾讯之UIDesigner
  3. 应用highcharts做直观数据统计
  4. RabbmitMQ集群搭建流程
  5. java javaScript实现遮罩层 动态加载
  6. messagebox在最顶层写法
  7. Bitmap 格式
  8. Java报错信息 java.lang.SecurityException: Prohibited package name: java.xxx
  9. 微信网页授权获取用户openid及用户信息
  10. 【java工具】java常用工具
  11. entity framework异常 The specified cast from a materialized &#39;System.Int32&#39; type to the &#39;System.String&#39; type is not valid
  12. jquery实现右键菜单
  13. CentOS SVN服务器管理多项目
  14. centos 打包报错License for package Android SDK Build-Tools 25.0.3 not accepted
  15. 微信h5支付“网站域名ICP备案主体与商户号主体不一致”的解决方法,H5微信支付 授权函下载
  16. 检测QQ在线状态脚本(20141022测试成功)
  17. [BZOJ4557][JLOI2016]侦察守卫(树形DP)
  18. Sublime key
  19. kaggle kernel使用指南
  20. 利用json2html将json数据填充到html模板

热门文章

  1. windows下Keras框架搭建
  2. SQL基本语句:2.基本表
  3. hook的本质就是在本原可执行文件中加东西
  4. 【AnjularJS系列6 】 过滤器
  5. ZBrush中2.5D笔刷
  6. ZBrush为电影制作设计独特的生物概念
  7. CodeForces-366C Dima and Salad 对01背包的理解 多个背包问题
  8. [LeetCode] 242. 有效的字母异位词 valid-anagram(排序)
  9. crm 系统项目(一) 登录,注册,校验
  10. 安装NexT主题