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.
|
|
|
|
|
### 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以后，再全局洪水覆盖一次，找出连通块的数量最大值，也是一样的。
|
|
|
|
|
|
|
