2023.11.10 信息学日志
1. CF1613E Crazy Robot
题目描述
https://www.luogu.com.cn/problem/CF1613E
题目概况
来源：Codeforces
洛谷难度： 绿题 \color{green}绿题 绿题
CF难度： 2000 2000 2000
标签：搜索 性质
思路点拨
正着去想一个点是否能走到实验室很难。“正难则反”——引自《数学胡老师语录》
从实验室出发去遍历周围的节点，如果一个节点是必到实验室节点，满足以下性质：
- 其遍历到周围 4 个节点至多有一个是新扩展到并且未判定其必到实验室可能性的。
- 其余的 3 个有 4 种情况可供选择。已确认必到实验室节点、障碍物节点、实验室节点、界外。
因此 bfs 从实验室遍历一遍即可解决该题。
AC。