首页 > 学院 > 开发设计 > 正文

dfs随笔,迷宫

2019-11-08 18:40:18
字体:
来源:转载
供稿:网友

剪枝:

1、如果可走的块数小于T,则肯定不能到达

2、奇偶性剪枝

可以把map看成这样:0 1 0 1 0 11 0 1 0 1 00 1 0 1 0 11 0 1 0 1 00 1 0 1 0 1从为 0 的格子走一步,必然走向为 1 的格子从为 1 的格子走一步,必然走向为 0 的格子即:  0 ->1或1->0 必然是奇数步  0->0 走1->1 必然是偶数步 结论:

  所以当遇到从 0 走向 0 但是要求时间是奇数的,或者, 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达!


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表