2023.11.10 信息学日志

1. CF1613E Crazy Robot

题目描述

https://www.luogu.com.cn/problem/CF1613E

题目概况

来源：Codeforces

洛谷难度：$绿题$

CF难度：$2000$

标签：搜索 性质

思路点拨

正着去想一个点是否能走到实验室很难。“正难则反”——引自《数学胡老师语录》

从实验室出发去遍历周围的节点，如果一个节点是必到实验室节点，满足以下性质：

• 其遍历到周围 4 个节点至多有一个是新扩展到并且未判定其必到实验室可能性的。
• 其余的 3 个有 4 种情况可供选择。已确认必到实验室节点、障碍物节点、实验室节点、界外。

因此 bfs 从实验室遍历一遍即可解决该题。

AC。