题目大意:老鼠的起点在S,出后在D,X是墙壁不能通过,.可以通过。出口在第T时刻开启,老鼠必须在这这个时刻到达出口,中途不能停留。
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized
that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the
T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for
more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the
maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.
Output
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise.
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES
这个题难的到不是DFS,而是剪枝的应用。刚开始总是超时,后来还是再网上看了些代码,加了一些剪枝条件才没超时。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
char map[7][7];
int m, n, t;
int startx, starty, endx, endy; //定义开始点,和结束点
int dir[4][2] = { { 0, -1 }, { 1, 0 }, { -1, 0 }, { 0, 1 } };
int escape; //是否逃脱标识
//求绝对值。
int myabs(int a) {
return a < 0 ? -a : a;
}
void dfs(int x, int y, int time) {
//重要的剪枝,减少搜索量。 否则超时
//相隔的距离不能太大,否则不可达。相隔的距离和剩余时间,应该同为奇数或偶数。
int temp = myabs(x - endx) + myabs(y - endy) - (t - time);
if (temp > 0 || temp % 2)
return;
int i;
for (i = 0; i < 4; i++) {
int tempx = x + dir[i][0];
int tempy = y + dir[i][1];
if (map[tempx][tempy] == 'D' && time == t - 1) {
escape = 1;
return;
}
if (map[tempx][tempy] == '.' && tempx >= 0 && tempx < n && tempy >= 0
&& tempx < n) {
map[x][y] = 'X';
dfs(tempx, tempy, time + 1);
map[x][y] = '.';
if (escape) //如果已经逃脱,就直接返回。
return;
}
}
}
int main() {
while (1) {
scanf("%d %d %d", &m, &n, &t);
if (0 == m)
break;
getchar();
int wall = 0;
int i,j;
for ( i = 0; i < m; i++) {
for ( j = 0; j < n; j++) {
scanf("%c", &map[i][j]);
if ('S' == map[i][j]) {
startx = i;
starty = j;
} else if ('D' == map[i][j]) {
endx = i;
endy = j;
}else if('X' == map[i][j]){
wall++;
}
}
getchar();
}
//第一次剪枝
if(n*m - wall <= t){
printf("NO\n");
continue;
}
escape = 0;
dfs(startx, starty, 0);
if (escape)
printf("YES\n");
else
printf("NO\n");
// break;
}
return 0;
}
分享到:
相关推荐
深度学习模型部署与剪枝优化实例视频教程下载。深度学习模型部署与剪枝优化实例课程旨在帮助同学们快速掌握模型部署与优化方法。 主要包括两大核心模块: 1.基于深度学习框架PyTorch与Tensorflow2版本演示模型部署...
搜索剪枝,全新讲解,覆盖面广,易懂,有使用价值,适用于noip,省赛,noi。。。。。
博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,...
该程序能够实现录入一个数独(空白部分用0代替),利用深度优先搜索算法在较短时间内给出数独的其中一个解并打印输出在屏幕上。该程序所用的深搜算法较为初级,未经剪枝优化,大家可以自行对其进行优化。 该程序运用...
acm-ICPC 搜索算法DFS和BFS文件格式(ppt)经典算法“剪枝”等算法,深度优先搜索和广度优先搜索。
无人驾驶深度学习模型组合剪枝算法.pdf
搜索方法中的剪枝优化,挺好的,希望对大家有用。
深度学习模型部署与剪枝优化实例课程旨在帮助同学们快速掌握模型部署与优化方法。
基于高效的主存索引Δ-tree设计了一种新的kNN查询算法NR_DF_knn_Search,该算法采用非递归方式深度优先搜索Δ-tree中距离查询点较近的叶子节点,能够快速找到较优的kNN候选,更新修剪距离,加大剪枝力度,缩小搜索...
当搜索的有上限且不大时,选择用深搜会很方便,不过深搜的缺点就是耗时(当然也不是特别的耗时,一般深搜问题不会TLE,如果实在超时了,用其他的方法吧),深搜和回溯和剪枝一直都是相互在一起的,我语文太差,说不...
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
ACM中的回溯法:搜索是人工智能中的一种基本方法,也是信息学竞赛选手所必须熟练掌握的一种方法。我们在建立一个搜索算法的时候,首要的问题不外乎两个: 1. 建立算法结构。 2. 选择适当的数据结构。 然而众所周知的...
提出一种基于动态减枝策略的深度优先搜索算法(Depth First Search based on Dynamic Pruning,DP-DFS),该算法构建一个二维矩阵,每搜索一个节点,比较当前路径的权值和与矩阵中已保存的权值,如果当前路径的权值...
支持以下的剪枝方法,代码一键运行,并配有md文档说明: (1) lamp 剪枝 (2) slimming 剪枝 (3) group slimming 剪枝 (4) group hessian 剪枝 (5) Taylor 剪枝 (6)Regularization 剪枝 等等
NULL 博文链接:https://chuanwang66.iteye.com/blog/1462968