迷宫问题：hdoj1010 DFS--剪枝实现

hdoj1010：迷宫问题：DFS-剪枝实现

#include <iostream>
#include <math.h>
using namespace std;
int N,M,T,di,dj,escape;
char map[10][10];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
void dfs_search(int si,int sj,int step)
{
	int newi,newj;
	if(si==di && sj==dj && step==T)
		escape=1;
	if(escape==1)
		return;
	int temp=T-step-abs(si-di)-abs(sj-dj);//剪枝②
	if(temp<0 || temp&1)
		return;
	for(int i=0;i<4;i++)
	{
		newi=si+dir[i][0];
		newj=sj+dir[i][1];
		if(map[newi][newj]!='X')
		{
			map[newi][newj]='X';
			dfs_search(newi,newj,step+1);
			map[newi][newj]='.';
		}
	}
}

void main()
{
	int si,sj;
	while(1)
	{
		int wall=0;
		cin>>N>>M>>T;
		if(N==0 && M==0 && T==0)
			break;
		for(int i=0;i<=N;i++)
			map[i][0]=map[i][M+1]='X';
		for(int i=1;i<=M;i++)
			map[0][i]=map[N+1][i]='X';
		for(int i=1;i<=N;i++)
			for(int j=1;j<=M;j++)
			{
				cin>>map[i][j];
				if(map[i][j]=='S')
				{si=i;sj=j;}
				else if(map[i][j]=='D')
				{di=i;dj=j;}
				else if(map[i][j]=='X')
					wall++;
			}
			if(T>=N*M-wall)//剪枝①
			{
				cout<<"NO"<<endl;
				continue;//情况处理干净
			}
			map[si][sj]='X';
			escape=0;
			dfs_search(si,sj,0);
			if(escape==1)
				cout<<"YES"<<endl;
			else
				cout<<"NO"<<endl;
	}
}

基于深度优先搜索的回溯算法（递归剪枝及奇偶性剪枝好题！）：HDOJ 1010 - Tempter of the Bone

2011-03-12 21:24

题目大意

给出起始位置和终点位置，要求在指定的时间刚好达到终点，每移动一步为一秒钟，并且不能返回。

题目分析

1. 要求在指定时间内达到，唯一想法就是能不能枚举出所有的抵达方案，再通过检查时间是否吻合得到结果。这就自然得到了用 DFS 进行搜索。

2. DFS 搜索完成后，提交发现超时，看样子还得剪枝才行。无奈啊，百度或Google一下喽。

3. 剪枝方法1：奇偶性剪枝

现在假设所在位置(x,y) 与目标位置 (dx,dy)。

如果abs(x-y)+abs(dx-dy)为偶数，则说明abs(x-y) 和 abs(dx-dy)的奇偶性相同，需要走偶数步。

如果abs(x-y)+abs(dx-dy)为奇数，那么说明abs(x-y) 和 abs(dx-dy) 的奇偶性不同，需要走奇数步。

理解为abs(x-dx)+abs(y-dy) 的奇偶性就确定了所需要的步数的奇偶性！

而(t-sec) 表示剩下还需要走的步数，由于题目要求要在 t 时恰好到达，那么 (t-sec) 与abs(x-y)+abs(dx-dy) 的奇偶性必须相同。

因此 temp= t-sec-abs(x-dx)-abs(y-dy) 必然为偶数！

4. 剪枝方法2：整个图可走的block应该大于指定的时间。

解决思路

首先，读取数据，同时就记录起点和终点各自的下标值。然后，从起点开始进行深度优先搜索。若当前节点是终点，且正好走了t步，则终止递归调用，并直接返回结果。若当前节点不是终点，且还有其它可走节点存在，则将当前节点标记为已走，同时将该节点作为新的当前节点，继续深度优先遍历；否则，修改回当前节点的原始状态，同时回溯若干步直到有新的相邻节点未走过。
测试用例

// 特殊测试

1. n*m-wall <= t , 奇偶性

2 2 2

SD

XX

NO

2. 奇偶性

2 2 3

SD

..

YES

3. 可走的block的总数小于时间

2 3 2

SDX

..X

NO

// 边界测试

6 6 10

S.....

......

......

......

......

.....D

YES

源代码

请点击链接（由于长度限制，只能将代码分离了。给你带来不便，真是抱歉！）

教训

1. 在 dfs() 的第一行缺少“if(escape) return;”语句，导致找到结果后不能直接终止递归调用，导致超时问题。理由是：如果缺少该行，这个 dfs 被前一个 dfs 调用，在这个返回的时候，前一个 dfs 并不能立刻返回。要想立刻返回，必须把它单独作为返回条件。这也说明该题的递归调用深度非常高。

2. 如果从数组的下标 0 开始存储数据，也会导致超时问题。无非是几个判断条件不一样，难道真的要求这么高？

3. 用搜索一般都要剪枝！

题目变形

1. 对于第一个变化，只要将给定时间的终止条件由“sec == t”改成“sec <= t”即可，变化部分代码如下所示：

// 终止条件

if(sec <= t && ci == di && cj == dj) {// Success!

escape = true;

return;

}

2. 对于第二个变化，思路是通过 BFS 搜索，第一次达到终点即是答案。

3. 对于第三个变化，奇偶性剪枝就不能满足了。所以，在第一个变化的基础上，将奇偶性剪枝的相关代码去掉即可。

题目原文：HDOJ1010 Tempter of the Bone

知识补充

回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”的寻找解的方法，就称作“回溯法”。

用回溯算法解决问题的一般步骤为：

一、 定义一个解空间，它包含问题的解。

二、 用适于搜索的方式组织该空间。

三、 用深度优先法搜索该空间，同时利用限界函数避免移动到不可能产生解的子空间。

回溯算法有一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。因此，该算法的空间需求为O(从开始节点起最长路径的长度)。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以，如果要存储全部解空间的话，再多的空间也不够用。

回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点（或起始节点）出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解（本题就属于该类型！）时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

参考资料：

1. 算法系列——回溯算法

2. 回溯——百度百科

参考资料

1. 刘春英——（HDUACM2010版_11）搜索入门.rar

2. HDOJ1010 Tempter of the Bone--DFS+奇偶剪枝

3. HDOJ 1010 Tempter of theBone（迷宫搜索）

4. 搜索与剪枝

参考资料：http://hi.baidu.com/bert825/blog/item/35f219649ea656ef431694fc.html