今天看到一個(gè)算法題端朵，題目呢是長這個(gè)樣子的：
豬場(chǎng)有一個(gè)x*y的網(wǎng)格盒子，網(wǎng)格的行編號(hào)為0~x-1蘸劈，列編號(hào)為0~y-1吆你。每個(gè)格子至多可以放一塊蛋糕弦叶，任意兩塊蛋糕之間的歐幾里得距離不能等于2。對(duì)于兩個(gè)格子坐標(biāo)（x1,y1),(x2,y2)的歐幾里得距離為((x1-x2)^2+(y1-y2)^2)的算術(shù)平方根妇多，豬場(chǎng)老板想知道最多可以放多少塊蛋糕在網(wǎng)絡(luò)格子里伤哺。
輸入描述：
x>=1,y<=1000
輸出描述：
輸出一個(gè)最多可以放的蛋糕數(shù)和網(wǎng)格的情況。
輸入例子：
x=3者祖，y=2
輸出例子：
4
我的思考：
若要滿足題目條件立莉，同一行的兩個(gè)蛋糕要隔兩行以上，且同一列的蛋糕要隔兩列以上七问。
要滿足最大化的條件蜓耻，則同一行的兩個(gè)蛋糕隔兩行，同一列的蛋糕隔兩列械巡。
經(jīng)過演算刹淌，一種是2*2方塊組每隔兩行或者兩列鋪列開來，另一種是對(duì)角線*2每隔兩個(gè)對(duì)角線鋪列開來讥耗。本質(zhì)其實(shí)是一樣的有勾，都是滿足上述最大化的條件。
我實(shí)現(xiàn)了第一種方案：
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("最大的蛋糕數(shù)為:"+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++;
?}
}
輸出結(jié)果為：
最大的蛋糕數(shù)為: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]
總結(jié)：像今天的網(wǎng)格問題和我之前分享的Wikioi問題葛账，都可以通過二維數(shù)組的簡(jiǎn)單比較實(shí)現(xiàn)柠衅，記得注意邊界值的判斷哦皮仁。
我是Wikioi推送門：Wikioi的簡(jiǎn)單實(shí)現(xiàn)
