题目:http://acm.hdu.edu.cn/showproblem.php?pid=1010
解题过程:
问题:
(1):
在发现当前节点无法到达时,这点弹出栈,并且把这点的标记重新刷为'.'
(2):
如何在dfs中既要保证到达又要使时间正好呢?? 在函数中通过这种形式实现:
dfs(int si,int sj,int cnt) 就是用cnt来记录当时的时间,并且在
if( si==di && sj==dj && cnt==t )
{
escape = 1;
return;
}
的时候 即当前点到达了终点并且时间恰好等于题目所给限制时间时,跳出
并且escape标记为真
(3):
如何让一个点有顺序地遍历它四周地能到达的点呢??聪明并且简短的方法是设施一个dir[4][2] 数组 控制方向并且设置它的值为dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};遍历的时候用for(int i = 0; i < 4; ++i)就非常方便了
(4):
千万要注意的是节点越界的情况, dfs(int si,int sj,int cnt)的时候一定要把 si, sj 控制在给你的矩阵内 在后面会提到一个我的列子 就是因为访问了[0, -1]的位置导致了其
他数据被更改
(5)
关于剪枝,没有剪枝的搜索不太可能。本题一个是奇偶剪枝,一个是路径剪枝。
奇偶剪枝:
把矩阵标记成如下形式:
0,1,0,1,0
1,0,1,0,1
0,1,0,1,0
1,0,1,0,1
很明显,如果起点在0 而终点在1 那显然 要经过奇数步才能从起点走到终点,依次类推,奇偶相同的偶数步,奇偶不同的奇数步在读入数据的时候就可以判断,并且做剪枝,当然做的时候并不要求把整个矩阵0,1刷一遍,读入的时候起点记为(Si,Sj) 终点记为(Di,Dj) 判断(Si+Sj) 和 (Di+Dj) 的奇偶性就可以了
路径剪枝:
矩阵的大小是N*M 墙的数量记为wall 如果能走的路的数量 N*M - wall 小于时间T,就是说走完也不能到总的时间的,这显然是错误的,可以直接跳出了课件里面给过这题的标程,在dfs的过程中有个没提到的剪枝,就是记录当前点到终点的最短路,如果小于剩余的时间的话,就跳出这个剪枝我觉得更科学,它毕竟是动态的么,标程里面是这么写的:
temp = (t-cnt) - abs(si-di) - abs(sj-dj);
if( temp<0 || temp&1 ) return;
(下面最短路是参考别人的,等会了最短路再重新解决这个问题吧)
-------------------------------------------------------------------------------
其中求当前点到终点的最短路是这样 abs(si-di) - abs(sj-dj) 这个就比较粗糙了 明显没有考虑到碰到墙要拐弯的情况那求最短路有没有什么好办法呢?我曾经想到过用 Dijkstraq求最短路的 ,明显大才小用,在论坛里看到一个方法觉得可
以用在这里
给定下例:
S.X.
..X.
..XD
....
每个点到终点的最短路是不是这样呢:
S6X2
65X1
54XD
4321
这怎么求呢??从终点开始遍历整个数组,终点是0,它周围的点都+1,墙就不计数,依次类推,就能求得这个矩阵的一个最短时间矩阵,在dfs的时候比较当前点到终点的最短路,
如果大于剩余时间的话就跳出
这个方法的预处理还是非常快的,我没有用过,但是感觉会非常有用处.
--------------------------------------------------------------------------------
(6)
在做这题的时候,我碰到过一个神奇的事情,在程序运行至下面代码时
if( map[ si+dir[i][0] ][ sj+dir[i][1] ] != 'X')
map[ si+dir[i][0] ][ sj+dir[i][1] ] = 'X';
T被改变了!! 这丝毫和T没有关系啊,怎么改变T的值呢??
原来在起点map[0][0]进入时,我没有注意到map[ si+dir[i][0] ][ sj+dir[i][1] ] 实际做的是map[0][-1] = 'X'; 很危险的一个赋值,书本上千万次强调的东西让我碰上了,这个地方我找了很久,因此我觉得有必要单独列出来提醒自己 所以循环都是从1开始
代码如下:
分享到:
相关推荐
HDU 1010-2500解题报告,ACMer可以借鉴一下
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
hdu2000-2014ac代码,虽然只有几道,但都是简单的
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
杭州电子科技大学online judge (hdu)第十一卷 2000 - 2099 题目集 doc 格式的,希望大家喜欢!
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
解题报告|ACM|程序设计参考程序以及题目的分析
ACM程序设计题目分析以及AC的源码
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
最精准的答案(本人做对的题目拿上来给大家呈现)!不要忘记是C++编的
ACM题库,一些题目和答案,以及解题报告,传上来共享
我去年暑假花了5天,把杭电ACM网站上2000到2099这100道题全AC了,又花了10来天精心写解题报告。 里面包括题目、解题思路、编程技巧以及参考源码。所有代码都是使用C/C++写的。 最近整理资料时无意间发现,打包...
杭电OnlineJudge 200-2099的解题报告
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]