2010年上海世博会世界名画陈列馆由个排列成矩形阵列的陈列室组成。为防止名画被盗，需要在陈列室中设置监控探头。每个探头除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的前、后、左、右4个陈列室

2010年上海世博会世界名画陈列馆由个排列成矩形阵列的陈列室组成。为防止名画被盗，需要在陈列室中设置监控探头。每个探头除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的前、后、左、右4个陈列室

测试用例： 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