913. Cat and Mouse

• 913. Cat and Mouse
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

这题DP没啥疑问，用dp[mouse][cat]表示状态当mouse在i，且cat在j的时候的状态

每次做BFS, 对于cat来说，当所有的从底下populate上来的result:

1. 全都是老鼠赢，那没办法
2. 有一个draw，那肯定选draw走
3. 有一个猫赢，优先选这个

Pitfall

这题目坑多

1. 猫不能进洞
2. 老鼠不要自投罗网，就是不能去猫的洞

Solution