狗哥热乎乎备考被店面

bdhmwzfa 发表于 2018-10-28 19:36
这种做法不一定对
原题中给了坐标系范围，如果人家maxy都没有2h大怎么办？而且我谨慎怀疑这个reflection ...

坐标范围只要保证有 h 就好吧？reflection principle只是假想对称一下，没有要真走过去。

Zpeace 发表于 2018-10-28 20:36
坐标范围只要保证有 h 就好吧？reflection principle只是假想对称一下，没有要真走过去。

我理解的镜像，是可以将原来结果中的某一类步骤，映射到新的一类步骤中去
假如说走到(maxx, 0)，那么可以知道，向左走和向右走的步数一定是一样多的，而且因为越过了h，所以可以知道steps to right > h and steps to left > h
那么如何将向左的步骤映射到向右？选出来的向左的步骤应该少于h，那该选哪些步映射呢？所以肯定不是唯一映射的
我实际写了程序，如果你按照我前面提到的方法写一遍，再按照映射的方法写一遍，对比一下会发现两者结果不一样，而且maxy与h差的越大结果差的越多，就是因为maxy越大，越过h这条线之后可以向右走的越多，相应的向左走的也就越多，映射越不准确。

bdhmwzfa 发表于 2018-10-29 09:54
我理解的镜像，是可以将原来结果中的某一类步骤，映射到新的一类步骤中去
假如说走到(maxx, 0)，那么可 ...

嗯，你说到了我没想到过的。镜像是 路径第一个到达h之后上下镜像。所以follow up 相当于是求走到 2h 的总共步数。

这是我开始没想到过的：如果坐标范围小于2h，是一定不可能在y 方向上先到达h，然后返回0的。

分享一个follow up的答法
y = h，我们就把原矩形切割成 一个小矩形 小矩形的高度为 h - 1
count(原矩形)  - count(y = h - 1) 即得到我们要的答案
因为一旦超过了h 怎么样都会碰到h这条边