题意:输入x,y,t.以及一个x行y列的地图,起点‘S’终点‘D’地板‘.’墙壁‘X’;判断能否从S正好走t步到D。

题解:dfs,奇偶性减枝,剩余步数剪枝。

ps:帮室友Debug的题:打错了两个字母。题目看错。没有初始化map。orz ...不过我dfs也不熟,更别说剪枝了。

//#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
int n, m, T;
int si, sj, ei, ej;
char a[][];
int map[][];
int dir[][] = { { , },{ -, },{ , },{ ,- } };
int check(int i, int j, int t) {
if (i< || i >= n || j< || j >= m || map[i][j] || a[i][j] == 'X') return false; return true;
}
bool dfs(int i, int j, int t) { if (i == ei&&j == ej&&t==T) return true;
if (t>=T) return false;
map[i][j] = ;
for (int k = ; k<; k++) {
int di = i + dir[k][];
int dj = j + dir[k][];
if (!check(di, dj, t + )) continue;
if (dfs(di, dj, t + ))
return true;
map[di][dj] = ;
}
return false;
}
int main() {
while (~scanf("%d%d%d", &n, &m, &T)) {
if (n == && m == && T == ) break;
memset(map, , sizeof(map));
for (int i = ; i<n; i++)
scanf("%s", a[i]);
int ok = ;
for (int i = ; i<n; i++) {
for (int j = ; j<m; j++) {
if (a[i][j] == 'D') {
ei = i; ej = j;
ok++;
}
if (a[i][j] == 'S') {
si = i; sj = j;
ok++;
}
if (ok == ) break;
}
if (ok == ) break;
}
if ((T - (abs(ei - si) + abs(ej - sj))) % || (T - (abs(ei - si) + abs(ej - sj)))<) printf("NO\n");
else if (dfs(si, sj,)) printf("YES\n");
else printf("NO\n");
}
return ;
}

最新文章

  1. Spark ML聚类分析之k-means||
  2. Check the difficulty of problems(POJ 2151)
  3. Linux Shell查看磁盘分区,内存使用,CPU使用率
  4. php ++a和a++
  5. Android (cocos2dx 网络访问)访问权限设置
  6. Cocos2d-JS地图性能问题
  7. D3D11_USAGE使用
  8. TCP/IP协议三次握手与四次握手流程解析(转载及总结)
  9. 使用Javascript 实现类
  10. PHP编程----猴子选大王
  11. 利用jQuery移除和添加图片
  12. 附录D——自动微分(Autodiff)
  13. ZOJ 2477 Magic&#160;Cube(魔方)
  14. 20165235 学习基础和C语言基础调查
  15. Android hdpi ldpi mdpi xhdpi xxhdpi适配详解
  16. xtrabackup备份mysql-2 增量备份
  17. R语言实战(四)—— 基本数据管理
  18. MenOS
  19. cmd下查看应用端口情况
  20. bootStrap中Tab页签切换

热门文章

  1. c 各种编译器(gcc clang)
  2. PHP代码审计笔记--文件包含漏洞
  3. Nginx 用户认证
  4. Nginx 72万连接性能测试(一)
  5. windows下nodejs与coffeeScript环境搭建
  6. Nginx/LVS/HAProxy负载均衡软件的优缺点
  7. IOS设计模式第八篇之键值观察模式
  8. 【git】 linux 环境安装git
  9. 【cs229-Lecture3】Logistic回归
  10. goldengate 过滤对某张表的复制操作