世界名画陈列馆（最少机器人问题和不重复监视问题）

陈列馆（最少机器人问题和不重复监视问题）"/>

世界名画陈列馆（最少机器人问题和不重复监视问题）

问题描述：

世界名画陈列馆问题。世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法。

目录

• • 最少机器人问题
  • 不重复监视问题

最少机器人问题

import java.util.Scanner;
import java.util.Arrays;/*** 世界名画陈列馆问题* 最少机器人* @author lzq**/
public class Test {static int[][] x=new int[10][10];      //这些数组大小可以根据自己需要改static int[][] y=new int[10][10]; static int[][] bestx=new int[10][10];  //x用来设置当前警卫，y用来表示监控情况，bestx返回最终结果static int n, m, best , k=0;public static void main(String[] args) {for(;;) {//新一轮开始，全部重置for (int i = 0; i < 10; i++) {Arrays.fill(x[i],0);Arrays.fill(y[i],0);Arrays.fill(bestx[i],0);}System.out.println("------------------------------------");System.out.println("请设置陈列馆区域:");System.out.print("m:");Scanner sc1 = new Scanner(System.in);m = Integer.parseInt(sc1.next());System.out.print("n:");sc1 = new Scanner(System.in);n = Integer.parseInt(sc1.next());compute(); //计算System.out.println("最少需要"+best+"个警卫！");for(int i = 1;i <= n; i++) {for(int j = 1;j <= m;j++) {System.out.print(bestx[i][j]+" ");}System.out.println();}}}/*** 在整个外面加上一圈，便于处理边界情况*/public static void compute() {best = m*n/3+2;for(int i = 0;i <= m+1;i++) {y[0][i] = 1;y[n+1][i] = 1;}for(int i = 0;i <= m+1;i++) {y[i][0] = 1;y[i][m+1] = 1;}search(1,0);}/*** 在(i, j)处设置一个警卫，并改变其周围受监控情况* @param i* @param j*/public static void change(int i,int j) {x[i][j] = 1;k++;y[i][j+1]++;y[i+1][j]++;y[i][j]++;y[i][j-1]++;y[i-1][j]++;}/*** 撤销在(i, j)处设置的警卫，并改变其周围受监控情况* @param i* @param j*/public static void restore(int i,int j) {x[i][j] = 0;k--;y[i][j+1]--;y[i+1][j]--;y[i][j]--;y[i][j-1]--;y[i-1][j]--;}/*** 回溯搜索* 从上到下，从左至右搜索没被监控的位置* @param i* @param j*/public static void search(int i,int j) {do {j++;if(j > m) {i++;j= 1;}}while(!((y[i][j] == 0) || (i > n)));//刷新警卫值if(i > n) {if(k < best) {best = k;for(int p = 1;p <= n;p++) for(int q = 1;q <= m;q++) bestx[p][q] = x[p][q];return;}}if(i < n) {           //结点pchange(i+1,j);search(i,j);      //递归搜索下一个点restore(i+1, j);  //恢复}if((y[i][j+1] == 0)) {   //结点qchange(i,j);search(i,j);      restore(i, j);}if(((y[i][j+1] == 0) && (y[i][j+2] == 0))) {  //结点qchange(i,j+1);search(i,j);      restore(i, j+1);}}}

运行结果：

不重复监视问题

import java.util.Scanner;/*** @ClassName ShiJieMingHua* @Description 世界名画问题* @Author lzq* @Date 2018/8/28 12:40* @Version 1.0**/
public class ShiJieMingHua {/*** 声明一个int类型的二维数组*/static int[][] array;/*** 初始化二维数组* @param length* @param width*/public static int[][] new_2Array(int length,int width){array = new int[length][width];for (int i = 0; i < length; i++) {for (int j = 0; j < width; j++) {array[i][j] = 0;}}return array;}/*** 判断此位置是否可以放置警卫* @param i* @param j* @return*/public static boolean isPut(int i,int j){if (array[i][j] == 0 && (i-1 < 0 || array[i - 1][j] != 1) && (j-1 < 0 ||array[i][j - 1] != 1) && (i+1 >= array.length || array[i + 1][j] != 1)  &&(j+1 >= array[i].length || array[i][j + 1] != 1)){return true;}return false;}/*** 设置警卫并且改变相应的值* @param i* @param j*/public static void set(int i,int j){// 此位置放置警卫array[i][j] = 2;//改变放置警卫能侦测到位置的值//上if (i > 0 && array[i - 1][j] == 0)	{array[i - 1][j] = 1;}//左if (j > 0 && array[i][j - 1] == 0){array[i][j - 1] = 1;}//右if (j+1 < array[i].length && array[i][j + 1] == 0)	{array[i][j + 1] = 1;}//下if (i+1 < array.length && array[i + 1][j] == 0)	 {array[i + 1][j] = 1;}}/*** 检查是否全部填满* @param length* @param width* @return*/public static boolean check(int length,int width){for (int i = 0; i < length;++i){for (int k = 0; k < width; ++k){if (array[i][k] == 0){return false;}}}return true;}/*** 全部回退* @param length* @param width*/public static void goBack(int length,int width){for (int i = 0; i < length; ++i){for (int k = 0; k < width; ++k){array[i][k] = 0;}}}/*** 警卫位置的填入* @param x* @param y* @param length* @param width*/public static void insert(int x,int y,int length,int width){//判断此位置是否越界if (x >= length || y >= width){return;}//判断此位置是否合适放置if (isPut(x, y)){set(x, y); //如果合适，设置警卫并且改变相应的值}//到下一行接着放置if (y == width-1){insert(x+1,0,length,width);}else{insert(x,y+1,length,width);}}/*** 逐一添置警卫* @param length* @param width*/public static void insert1(int length,int width){for (int i = 0; i < length;++i){for (int j = 0; j < width;++j){//往i,j位置添加insert(i,j,length,width);//判断是否填满if (check(length,width)){break;}else {//回退goBack(length, width);}}}}/*** 打印二维数组元素*/public static void show2(){for(int i = 0;i < array.length;i++) {for(int j = 0;j < array[i].length;j++) {System.out.print(array[i][j]+"\t");}System.out.println();}}public static void main(String[] args) {for(;;) {System.out.println("设置陈列馆:");System.out.print("行数m: ");Scanner sc1 = new Scanner(System.in);int m = Integer.parseInt(sc1.next());System.out.print("列数n: ");sc1 = new Scanner(System.in);int n = Integer.parseInt(sc1.next());new_2Array(m, n);insert1(m, n);show2();}}
}

运行结果：