(hdu step 4.3.1)Tempter of the Bone(在特定的时间约束下,判断是否能够从起点达到终点)

题目:

题目分析：

                “判断是否能够从起点达到终点”，这种题用BFS就能轻松搞定。然后这道题的特点就在于“在指定时间的约束下”。那么这时候我们可以使用DFS来做。   本来想自己写一下想法的。但是发现网上有人写的比我将要写的详细多了。所以投一下懒，用一下别人的总结。

1. 1010 temp of the bone
2. 
   
3. sample input:
4. 4 4 5
5. S.X.
6. ..X.
7. ..XD
8. ....
9. 
   
10. 问题：
11. (1):
12. 在发现当前节点无法到达时,这点弹出栈,并且把这点的标记重新刷为'.'
13. 
    
14. (2):
15. 如何在dfs中既要保证到达又要使时间正好呢?? 在函数中通过这种形式实现:
16. 
    
17. dfs(int si,int sj,int cnt) 就是用cnt来记录当时的时间,并且在
18. 
    
19. if( si==di && sj==dj && cnt==t )
20.     {
21.         escape = 1;
22.         return;
23.     }
24. 
    
25. 的时候 即当前点到达了终点并且时间恰好等于题目所给限制时间时,跳出
26. 并且escape标记为真
27. 
    
28. (3):
29. 如何让一个点有顺序地遍历它四周地能到达的点呢??
30. 聪明并且简短的方法是设施一个dir[4][2] 数组 控制方向
31. 并且设置它的值为dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
32. 
    
33. 遍历的时候用for(i:0->4)就非常方便了
34. 
    
35. (4):
36. 千万要注意的是节点越界的情况, dfs(int si,int sj,int cnt)的时候一定要把 si, sj 控制在给你的矩阵内 在后面会提到一个我的列子 就是因为访问了[0, -1]的位置导致了其
37. 
    
38. 他数据被更改
39. 
    
40. (5):
41. 读入矩阵的时候,可以采用for(i = 1; i <= N; i++)
42.                for(j = 1; j <= M; j++)
43.                 scanf("%c", &map[i][j]);       
44. 
    
45. 的方法,好处在于可以控制和计算每一个读入的数据,坏处是调试的时候对矩阵的观察不太方便,而且好像还会有错误,在2102"A计划"用这种方法读入数据时好像就会wa,
46. 
    
47. 另一种方法是for(i = 0; i < N; i++) gets(map[i]);
48. 这样读入的数据在调试观察的时候十分方便 gets()读入的默认为字符串,在vc调试的时候是显式的 可以直接观察矩阵 缺点是对矩阵中各个数据的计算和控制无法实现,需要读完后再遍历一遍
49. 
    
50. (6)
51. 能用bfs还是尽量用bfs 我不会bfs.... dfs的递归在调试的时候不是很方便,而且bfs要比dfs快,调试也要方便,因为它没有递归
52. 
    
53. (7)
54. 关于剪枝,没有剪枝的搜索不太可能,这题老刘上课的时候讲过两个剪枝,一个是奇偶剪枝,一个是路径剪枝
55. 
    
56. 奇偶剪枝:
57. 把矩阵标记成如下形式:
58. 0,1,0,1,0
59. 1,0,1,0,1
60. 0,1,0,1,0
61. 1,0,1,0,1
62. 很明显,如果起点在0 而终点在1 那显然 要经过奇数步才能从起点走到终点,依次类推,奇偶相同的偶数步,奇偶不同的奇数步
63. 在读入数据的时候就可以判断,并且做剪枝,当然做的时候并不要求把整个矩阵0,1刷一遍,读入的时候起点记为(Si,Sj) 终点记为(Di,Dj) 判断(Si+Sj) 和 (Di+Dj) 的奇偶性就可以了
64. 
    
65. 路径剪枝:
66. 矩阵的大小是N*M 墙的数量记为wall 如果能走的路的数量 N*M - wall 小于时间T,就是说走完也不能到总的时间的,这显然是错误的,可以直接跳出了
67. 
    
68. 课件里面给过这题的标程,在dfs的过程中有个没提到的剪枝,就是记录当前点到终点的最短路,如果小于剩余的时间的话,就跳出
69. 这个剪枝我觉得更科学,它毕竟是动态的么,标程里面是这么写的:
70. temp = (t-cnt) - abs(si-di) - abs(sj-dj);
71. if( temp<0 || temp&1 ) return;
72. 
    
73. 其中求当前点到终点的最短路是这样 abs(si-di) - abs(sj-dj) 这个就比较粗糙了 明显没有考虑到碰到墙要拐弯的情况
74. 那求最短路有没有什么好办法呢?
75. 
    
76. 我曾经想到过用 Dijkstraq求最短路的 ,明显大才小用,在论坛里看到一个方法觉得可以用在这里
77. 给定下例:
78. 
    
79. S.X.
80. ..X.
81. ..XD
82. ....
83. 
    
84. 每个点到终点的最短路是不是这样呢:
85. 
    
86. S6X2
87. 65X1
88. 54XD
89. 4321
90. 
    
91. 这怎么求呢??从终点开始遍历整个数组,终点是0,它周围的点都+1,墙就不计数,依次类推,就能求得这个矩阵的一个最短时间矩阵,在dfs的时候比较当前点到终点的最短路,如果大于剩余时间的话就跳出
92. 
    
93. 这个方法的预处理还是非常快的,我没有用过,但是感觉会非常有用处.
94. 
    
95. (8)
96. 在做这题的时候,我碰到过一个神奇的事情,在程序运行至下面代码时
97. 
    
98. if( map[ si+dir[i][0] ][ sj+dir[i][1] ] != 'X')           
99.     map[ si+dir[i][0] ][ sj+dir[i][1] ] = 'X';
100. 
     
101. T被改变了!! 这丝毫和T没有关系啊,怎么改变T的值呢??
102. 
     
103. 原来在起点map[0][0]进入时,我没有注意到map[ si+dir[i][0] ][ sj+dir[i][1] ] 实际做的是map[0][-1] = 'X'; 很危险的一个赋值,书本上千万次强调的东西让我碰上了,这个地方我找了很久,因此我觉得有必要单独列出来提醒自己
104. 
     

代码如下：

/*
 * a.cpp
 *
 *  Created on: 2015年2月24日
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 9;
char map[maxn][maxn];//地图矩阵.用于存储地图的情况

int n;//行数
int m;//列数
int t;//目标时间

int x1,y1;//起点
int x2,y2;//终点

int dir[4][2]={//方向矩阵
		{1,0},
		{-1,0},
		{0,1},
		{0,-1}
};

/**
 * 判断下一步是否合法
 */
bool check(int x,int y){
	if( x < 0 || x >= n || y <0 || y >= m){//如果坐标越界
		return false;//则表明下一步不合法
	}

	return true;//否则下一步合法
}


/**
 * DFS。
 * si:当前结点的行数
 * sj:当前节点的列数
 * cnt:到达(si,sj)是所用的时间
 */
bool dfs(int si,int sj,int cnt){
	if(si == x2 && sj == y2 && cnt == t){//如果在指定时间内到达目标点
		return true;//返回true
	}

	/**
	 * 如果当前结点越界。这个判断是不需要的。
	 * 加了还可能超时。因为是否越界的判断在产生下一节点的时候就已经做了
	 */
//	if(check(si,sj) == false){
//		return false;
//	}

	/**
	 *
	 * t-cnt:表示剩余时间
	 * abs(x2-si) + abs(y2-sj):从当前节点道目标节点所需要的时间
	 */
	int temp = (t - cnt) - (abs(x2-si) + abs(y2-sj));
	//最短路径剪枝
	if(temp < 0){//如果剩余时间不足以到达目标节点
		return false;//返回false,表示这条路径不成功
	}

	//奇偶剪枝
	if(temp&1){
		return false;
	}

	int i;
	for(i = 0 ; i < 4 ; ++i){//遍历当前节点的相邻结点
		int tempi = si+dir[i][0];//计算下一节点的坐标
		int tempj = sj+dir[i][1];

		if(check(tempi,tempj) == false){//如果计算出来的下一届点的坐标不合法
			continue;//则跳过这一结点,计算下一结点
		}

		if(map[tempi][tempj] != 'X'){//如果当前节点不是墙壁
			map[tempi][tempj] = 'X';//江当前节点设置为墙壁
			bool flag = dfs(tempi,tempj,cnt+1);//沿着这一节点往下搜

			if(flag == true){//如果这一条路径可行
				return true;//则返回true.表示目标节点可以到达
			}
			//当知心以下代码的时候表示通过这一节点无法到达目标节点

			map[tempi][tempj] = '.';//拿奖当前节点重新设置成'.'可用状态
		}
	}

	return false;//如果经过上面都无法找到一条路径.那么到现在的时候就已经表明目标节点无法到达
}


int main(){
	while(scanf("%d%d%d",&n,&m,&t) != EOF,n){
		int i;
		int j;
		for(i = 0 ; i < n ; ++i){
			cin >> map[i];
		}

		int wall = 0;//用于包村墙壁的数量

		for(i = 0 ; i < n ; ++i){
			for(j = 0 ; j < m ; ++j){
				if(map[i][j] == 'S'){//记录起点的位置
					x1 = i;
					y1 = j;
				}else if(map[i][j] == 'D'){//记录终点的位置
					x2 = i;
					y2 = j;
				}else if(map[i][j] == 'X'){//统计墙壁的数量
					wall++;
				}
			}
		}

		//路径剪枝
		int nums = n*m - wall;//计算可走的步数
		if(nums < t){//如果可走的步数<指定的时间
			printf("NO\n");//那么表明路已经走完了也还没有达到指定时间.name返回false.表示没有这样的一条路径
			continue;
		}

		map[x1][y1] = 'X';//奖起点设置为墙壁'x'
		bool result = dfs(x1,y1,0);//从起点开始遍历

		if(result == true){//如果resultweighttrue,表明有这么一条路径
			printf("YES\n");
		}else{
			printf("NO\n");//否则表明没有这样一条路径
		}
	}

	return 0;
}