解題思路：
由題意知任意兩塊蛋糕的歐幾里得距離不能等于2，也即有兩組關系：（1）x1 - x2 = 2(或-2)，y1 - y2 = 0；（2）y1 - y2 = 2(或-2)，x1 - x2 = 0；可理解為若開始放蛋糕的位置為（x,y）；則對于每一行來說（x + 2, y）處不能放蛋糕；對于每一列來說（x, y + 2）處不能放蛋糕，
一個較為簡單的數學問題，舉例就能發現規律，4為周期，如下圖：
我們也可定義一個二維陣列，不初始化，則其默認的值均為0；然后把不能放蛋糕的地方置為-1；最后還剩幾個0就表示可以放多少的蛋糕，
方法一：
找規律，不管是行還是列，只要有一個能夠被4整除，蛋糕數就為網格總數的一半；如果行跟列都不能被4整除，蛋糕數等于網格總數除以2，再加上1，
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int H = sc.nextInt();
int W = sc.nextInt();
int count = 0;
if (H % 4 == 0 || W % 4 == 0) {
count = H * W / 2;
} else {
count = H * W / 2 + 1;
}
System.out.println(count);
}
}
方法二：
直接遞推，把所有不能放蛋糕的地方置為-1；最后還剩幾個0就表示可以放多少的蛋糕，
import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int W = scanner.nextInt();
int H = scanner.nextInt();
int[][] arr = new int[W][H];//創建一個初始化為 0 的二維陣列
int count = 0;//計數器，將不能放蛋糕的地方置為 -1 ，最后剩幾個 0 就意味著可以放幾塊蛋糕
for (int i = 0; i < W; i++) {
for (int j = 0; j < H; j++) {
if (arr[i][j] == 0) {
count++;
if ((i + 2) < W) {//每一行不能放蛋糕的地方
arr[i + 2][j] = -1;
}
if ((j + 2) < H) {//每一列不能放蛋糕的位置
arr[i][j + 2] = -1;
}
}
}
}
System.out.println(count);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/278845.html
標籤：java