世界名画陈列馆由 n×m 个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右 4 个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,并且要求每一个陈列室仅受一个警卫机器人监视,且所用的警卫机器人数最少。写出回溯法对应的剪枝函数设计
时间: 2024-01-21 16:18:23 浏览: 30
剪枝函数:
1. 如果当前已经使用的警卫机器人数已经大于之前找到的最小值,则进行剪枝。
2. 对于每个陈列室,我们只需要考虑它的上和左两个方向是否有警卫覆盖即可,因为右方和下方的陈列室会在后面的搜索中被考虑到,避免重复计算。
3. 如果一个陈列室的上或左有警卫覆盖,则可以剪枝掉它,因为它已经被覆盖了。
4. 如果一个陈列室的上和左都没有警卫覆盖,则可以剪枝掉它,因为它无法被覆盖。
代码实现:
```python
def pruning(n, m, used, row, col):
# 如果已经使用的警卫数大于之前找到的最小值,则剪枝
if used >= min_guard:
return True
# 对于每个陈列室,只考虑上和左方向是否有警卫覆盖
if row > 0 and col > 0:
if guards[row-1][col-1] == 0 and guards[row-1][col] == 0 and guards[row][col-1] == 0:
# 上和左都没有警卫覆盖,则剪枝
return True
elif row == 0 and col > 0:
if guards[row][col-1] == 0:
# 左边有警卫覆盖,则剪枝
return True
elif row > 0 and col == 0:
if guards[row-1][col] == 0:
# 上面有警卫覆盖,则剪枝
return True
return False
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)