网格问题

今天看到一个算法题，题目呢是长这个样子的：

猪场有一个x*y的网格盒子，网格的行编号为0~x-1，列编号为0~y-1。每个格子至多可以放一块蛋糕，任意两块蛋糕之间的欧几里得距离不能等于2。对于两个格子坐标（x1,y1),(x2,y2)的欧几里得距离为((x1-x2)^2+(y1-y2)^2)的算术平方根，猪场老板想知道最多可以放多少块蛋糕在网络格子里。

输入描述：

x>=1,y<=1000

输出描述：

输出一个最多可以放的蛋糕数和网格的情况。

输入例子：

x=3，y=2

输出例子：

4

我的思考：

若要满足题目条件，同一行的两个蛋糕要隔两行以上，且同一列的蛋糕要隔两列以上。

要满足最大化的条件，则同一行的两个蛋糕隔两行，同一列的蛋糕隔两列。

经过演算，一种是2*2方块组每隔两行或者两列铺列开来，另一种是对角线*2每隔两个对角线铺列开来。本质其实是一样的，都是满足上述最大化的条件。

我实现了第一种方案：

package new2017;

import java.util.Arrays;

public class Wangge {
 private static int count = 0;
 public static void main(String[] args) {
  int x = 10, y = 10;
  int[][] a = new int[x][y];
  maxWangge(a);
 }
 public static void maxWangge(int[][] a){
  int x=a.length,y=a[0].length;
  for (int i = 0; i < x; i++) {
   for (int j = 0; j < y; j++) {
    if (i >= 2 && j >= 2) {
     if (a[i - 2][j] == 0 && a[i][j - 2] == 0) {
      addCount(a,i,j);
     }
    } else if (i >= 2 && j < 2) {
     if (a[i - 2][j] == 0) {
      addCount(a,i,j);
     }
    } else if (i < 2 && j >= 2) {
     if (a[i][j - 2] == 0) {
      addCount(a,i,j);
     }
    } else {
     addCount(a,i,j);
    }
   }
  }
  System.out.println("最大的蛋糕数为:"+count);
  for(int[] b : a){
   System.out.println(Arrays.toString(b));
  }
 }
 
 public static void addCount(int[][] a,int i,int j){
  a[i][j] = 1;
  count++;
 }
}

输出结果为：

最大的蛋糕数为:52

[1, 1, 0, 0, 1, 1, 0, 0, 1, 1]

[1, 1, 0, 0, 1, 1, 0, 0, 1, 1]

[0, 0, 1, 1, 0, 0, 1, 1, 0, 0]

[0, 0, 1, 1, 0, 0, 1, 1, 0, 0]

[1, 1, 0, 0, 1, 1, 0, 0, 1, 1]

[1, 1, 0, 0, 1, 1, 0, 0, 1, 1]

[0, 0, 1, 1, 0, 0, 1, 1, 0, 0]

[0, 0, 1, 1, 0, 0, 1, 1, 0, 0]

[1, 1, 0, 0, 1, 1, 0, 0, 1, 1]

[1, 1, 0, 0, 1, 1, 0, 0, 1, 1]

总结：像今天的网格问题和我之前分享的Wikioi问题，都可以通过二维数组的简单比较实现，记得注意边界值的判断哦。

我是Wikioi推送门：Wikioi的简单实现