题意:在一个坐标系的原点出发走k步回到原点,第i步走i个单位长度。有x个障碍,障碍不能经过或者停留。每一步结束的地方不能再作为结束的地方。求有多少中方案以及每个方案的移动序列(用wsne表示),按字典序输出。

分析:垃圾题面毁我青春!它竟然没有说清楚不能在停留过的点停留!

所以我们建立一个二维数组(起名叫mp)进行判重。mp[x][y]==1表示有障碍,mp[x][y]==2表示停留过。搜索时判断经过的每个点是否为障碍,再判断结束点是否停留过。

剪枝:如果当前距离原点的距离大于以后可以走的总距离,则停止继续搜索。

其实本题还可以继续优化:

1.使用中途相遇法,先走k/2步(或者说2k/1.414步),保存到大的点和上一步走的方向。再从原点走k/2(或者说1-2k/1.414)步,在上一次搜索到的点中寻找可行的“拼接”,生成行动序列。

2.使用前缀和优化判断移动是否可行的过程。对mp的每一行每一列计算前缀和,即可将每一个序列的均摊判断复杂度的O(N2)优化成O(N);

不过这两个优化只是特别小的优化,没有显著效果。第一个实在就不值得实现了。第二个实现后将300ms优化成了270mn也算是有点用吧

优化后代码↓