> 根据输入字符串可得到一个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
> 应该还有更好的剪枝
> 大牛指教!

• 这样判断最短路正确吗？ (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