codeforces edu1 D. Igor In the Museum

2015年12月4日 0 作者 CrazyKK

http://codeforces.com/contest/598/problem/D

题意:给第一个地图。 ‘.’是能走的,‘*’是不能走的。每个‘.’和’*’之间有一幅画,给出k个起点,问对于每组起点,最多能观察到多少副画。

思路:dfs.要注意即使只有一个‘*’,从不同方向访问仍然算不同的画。这样就不用标记画是否访问过了。一开始直接暴力dfs..TLE 10

然后发现,如果是在同一个联通快内,能看到的画的最大值是确定的。。如果之前有同一个联通快内的其他点dfs过得到过答案,那么下次就不用再dfs了。。。记得把之前的记过保存下来。。

我具体的写法是把某一次dfs进过的点的恒纵坐标都存起来。。。然后dfs结束后把更新这些沿途中经过的点的答案。。结果还是TLE 10

果然是记忆化写残了。。也不是写残了。。看了几个别人的代码。。。记忆化存的时候是按照某一次来存答案。。而我是按照某个点的坐标。。来存答案。果然还是要提高姿势水平啊。。。SAD