2010年上海世博会世界名画陈列馆由个排列成矩形阵列的陈列室组成。为防止名画被盗，需要在陈列室中设置监控探头。每个探头除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的前、后、左、右4个陈列室
- 提问者网友：活着好累
- 2021-05-07 13:31
- 五星知识达人网友：傲气稳了全场
- 2021-05-07 15:00
测试用例： Input Output
4 4 4
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
算法分析：
1、状态空间树：是一颗子集树，采用搜索的回溯算法框架求解。设一般从上到下、从左到右的顺序依次考察。用x[i,j] = 1表示陈列室(i,j)设置了警卫岗位；y[i,j] = 1表示该陈列室当前受警卫的监视。
2、 下界条件：设当前已设置的警卫数k，受监视的陈列室数为t，当前最少警卫数为best。估计出尚需设置的警卫数下界f(k,t)。如果f(k,t)>=best,删去这一结点及其子树。
3、 控制条件：设p q是状态空间树的2个不同节点。如果按照p q的某一关系，可以确定以q为根的子树解不优于以p为根的子树的解，则称结点p控制了结点q。
(1)在(i, j)处设置一个警卫，即x[i][j] = 1,相应于状态空间树中的一个节点q。在(i+1, j+1)处放置一个警卫，即x[i+1][j+1] = 1，相应于状态空间树中的另一个节点p。容易看出，p控制了q。由此总结出由上到下、由左到右的顺序依次检查每一个陈列室，已受监控的陈列室不用在设置警卫，避免了很多重复的搜索。
(2) 为了使(i,j)受到监视，可在(i+1,j) (i,j) (i,j+1)处设置警卫，设此时对应的结点分别是p，q，r。当y[i][j+1]=1时,p控制q；当y[i][j+1]=1且y[i][j+2]=1时，p控制r。所以应该按p->q->r的顺序扩展结点，并检测节点p对节点q和节点r的控制条件，及时剪去受控结点的子树。
具体实现及必要说明见代码。
其他测试用例及结果：
10 10
24
0 0 1 0 0 0 1 0 1 0
1 0 0 0 1 0 0 0 0 0
0 0 1 0 0 0 0 1 0 1
1 0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0 0 1
0 1 0 1 0 0 0 1 0 0
15 9
33
0 0 0 0 1 0 1 0 0
1 1 1 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0
0 1 0 1 0 0 0 1 0
0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1
0 0 0 0 1 0 1 0 0
0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0
1 1 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0
0 1 0 0 0 1 0 1 0
8 13
26
0 1 0 0 1 0 0 1 0 0 0 1 0
0 1 0 0 1 0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0 0 0
1 0 0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 1 0 0 1 0 1 0
6 20
30
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1
0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0
0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0