根据输入字符串可得到一个a*b的活动区域 一般的这个区域要比6*6小

因为棋盘的边框也可以看做wall 所以让活动区域贴着棋盘的角时可以得到最优
起始位置的枚举就是4次 远小于36次枚举

wall的枚举就在a*b的活动区域中进行就行
把wall之间的intersection和wall和input之间的cross剪枝掉
但有些wall的长度>max(a,b) 要再处理一下

枚举出wall和startpoint之后把B题的代码cp过来做BFS 但因为B题本身就是Spj题目所以直接得到的序列可能和输入字符串不同 就会出错
这时不用再做类似spj的判断 把B题的代码改一下就好了--把输入字符串第i步的方向作为BFS第i层的优先方向先压入队列即可(有点估价函数的感觉)

我就是这样剪枝的 G++ 93ms
应该还有更好的剪枝
大牛指教!

• 1435778 frkstyc 72K 15MS GCC 5965B ---- frkstyc大牛怎么做到这么快的？ (417) alpc04 2006-08-07 17:38:12
  • 这样判断最短路正确吗？ (45) alpc04 2006-08-07 22:37:05
    • 卡四个角是错的 (47) frkstyc 2006-08-07 22:43:07
      • 如果不卡四个角的话 那边框岂不被浪费？ (0) alpc04 2006-08-07 22:45:21
        • 和边框没有关系 (0) frkstyc 2006-08-07 22:47:03
          • 边框可以看做墙的啊 (0) alpc04 2006-08-07 22:49:49
            • 但是有可能根本放不到角上，这个题还有其他约束的 (0) frkstyc 2006-08-07 22:53:10
          • 最多只有三堵墙 如果那种不用放在角上的情况移动到角上去的时候 多出来的需要处理的墙找一个边框放就是了 有四个边框呢总可以放下 (0) alpc04 2006-08-07 22:57:51
            • 你的墙全放别处去最短路就不一定是那个样子了 (0) frkstyc 2006-08-07 22:59:11
              • 想不通 如果是那样的话 那放不放角上又有什么关系呢 是活动区域贴角不是说墙贴角 (0) alpc04 2006-08-07 23:04:07
                • 区域的位置和墙的位置不是互相独立的 (0) frkstyc 2006-08-07 23:23:41
• Re:剪枝方法大致见内 --- 修正一下 (180) alpc04 2006-08-08 00:55:24
  • 一定在边上,有4边而只有3面墙 (204) number 2006-08-08 01:40:29