You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1.1 KiB
1.1 KiB
2、青蛙跳木桩
Q:为什么写的伪代码与真正实现的代码，检查是不是终点的位置不一样？
(1)在检查下一个可达位置时，直接检查下一个位置是不是终点 (2)在检查下一个可达位置时，不管下一个位置是不是终点，直接再次入队列，直到它从队列中弹出时再检查。
这两种作法，从效率上讲，肯定是第1种更佳。参看代码进行理解。
3、翻卡片
为什么存在某种特定的情况比如 B B A A A B B A A A A A A A A A A A A A
Q：此时，我们选择了左上角的B，然后以此点为起点，进行洪水覆盖，结果，发现只能覆盖掉1个点，可是，此时整个图形的最大覆盖值应该是 16 个！ 这不就错了吗？
A: 不用怕，因为我们的程序还在继续，会走到第2个B点，此时就能获取到17个，比刚才的肯定要大，这个结果最终会替换掉刚才被封成边缘的B。也算是一种贪心策略吧。当然，我们也可以在假定某个位置是A以后，再全局洪水覆盖一次，找出连通块的数量最大值，也是一样的。