网格问题

今天看到一个算法题,题目如下:

猪场有一个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

我的思考:

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

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

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

我实现了第一种方案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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++;
 }
}

输出结果为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
最大的蛋糕数为: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的简单实现

作者:有奶喝先森
链接:http://www.jianshu.com/p/ca6c5f3c3950
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。