算法设计与分析: 5

算法设计与分析: 5"/>

算法设计与分析: 5

5-20 世界名画陈列馆问题（不重复监视）

问题描述

世界名画陈列馆由 m×n m × n $m\times n$ 个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与 它所在的陈列室相邻的上、下、左、右 4 个陈列室。试设计一个安排警卫机器人哨位的算法， 使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下，并且要求每一个陈列室仅受一 个警卫机器人监视，且所用的警卫机器人数最少。

设计一个算法，计算警卫机器人的最佳哨位安排，使得名画陈列馆中每一个陈列室都仅 受一个警卫机器人监视。且所用的警卫机器人数最少。

数据输入：
第一行有 2 个正整数 m 和 n (1≤m,n≤20)。

Java

package Chapter5HuiSuFa;import java.util.Scanner;public class ShiJieMingHuaChenLieGuanBuChongFuJianShi {private static int m,n;private static int[][] x;private static int best;public static void main(String[] args){Scanner input = new Scanner(System.in);while (true){n = input.nextInt();m = input.nextInt();x = new int[n+1][m+1];compute();}}private static void compute(){boolean ok = false;if(n == 1){int k = m/3;if(m%3 == 1)for(int j=0; j<=k; j++)x[1][3*j+1] = 1;else{if(m%3 == 0) k--;for(int j=0; j<=k; j&#