简单迷宫变形:一次最多走k步(神奇剪枝
题目
在简单的迷宫问题一次只能走一步的基础上改变了一次可以1到k步,求最少次数。
解题思路
暴力的话不难,在枚举四个方向后,每个方向乘上倍数即可。
part1
核心代码:
1 | for (int i = 0; i < 4; i++)//枚举四个方向 |
part2
啪一下很快啊 ,TLE之后就发现应该是vis的continue剪枝不够狠。然后想了一下,似乎这个continue可以直接修改成break。因为这个点既然之前已经访问过,那肯定会比现在访问更优(或一样优)然而事实证明,所有未经证明的猜想都是耍流氓。
遂修改成break,代码:
1 | for (int i = 0; i < 4; i++)//枚举四个方向 |
part3
啪一下很快啊WA了(梅开二度.jpg),之后想了很久,感觉思路没问题,但是隐隐之中似乎找到了问题所在,可是又说不出,然后加了一个dis
数组,dis[x][y]
表示走到点(x,y)的最小步数。
在此基础上,如果下一步访问的点之前已经访问过时(也即vis[xx][yy]==true)
,考虑step+1
和dis[xx][yy]
的关系。
由于队列的性质,很显然的两者只有两种关系:
- step+1==dis[xx][yy]
这时,我们选择continue
- step+1>dis[xx][yy]
这时,我们选择break
原因看最后的数据
然后下面是修改后的代码:
1 | for (int i = 0; i < 4; i++)//枚举四个方向 |
part4
AC代码:
1 |
|
后言
AC之后,就开始造数据,皇天不负有心人,下面是一组数据:
1 | 6 11 1000 |
如果我们在BFS的mov数组中,优先是向右走,那么前三次移动形成的dis数组如下所示:
1 | 6 11 1000 |
下一次移动是左下角的那个3,然而,将访问的4已经visited
,并满足dis[xx][yy]==step+1
(4=3+1),对应了上面的情况一,选择continue
而不是break
。
写完这个题感觉好爽啊