import java.util.Scanner; public class Main { // 全局变量：网格行列、最大放置数、主/副对角线占用标记 private static int n, m, max = 0; // 主对角线(i-j)：范围[-9,9]，偏移10转成[1,19] private static boolean[] diag1; // 副对角线(i+j)：范围[0,18]（n,m≤10，最大9+9=18） private static boolean[] diag2; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 行（水平区域数） m = sc.nextInt(); // 列（垂直区域数） sc.close(); // 初始化对角线标记数组，大小20足够覆盖所有情况 diag1 = new boolean[20]; diag2 = new boolean[20]; // 从第0行第0列开始DFS，当前已放置0个 dfs(0, 0, 0); System.out.println(max); } /** * 逐格DFS核心方法 * @param i 当前行 * @param j 当前列 * @param cnt 当前已放置的传教士数量 */ private static void dfs(int i, int j, int cnt) { // 剪枝：剩余格子数+当前数 ≤ 已找最大值，直接返回（避免超时） int left = n * m - (i * m + j); if (cnt + left <= max) return; // 递归终止：遍历完所有行，更新最大值 if (i >= n) { if (cnt > max) max = cnt; return; } // 处理列换行：当前列遍历完，到下一行第0列 int ni = i, nj = j + 1; if (nj >= m) { ni = i + 1; nj = 0; } // 选择1：当前格子不放，直接遍历下一个 dfs(ni, nj, cnt); // 选择2：当前格子放，先判断对角线是否未被占用（核心冲突判断） int d1 = i - j + 10; // 主对角线偏移，避免负数索引 int d2 = i + j; // 副对角线直接用 if (!diag1[d1] && !diag2[d2]) { // 标记对角线为占用 diag1[d1] = true; diag2[d2] = true; // 递归下一个格子，数量+1 dfs(ni, nj, cnt + 1); // 回溯：恢复标记（DFS必备，否则冲突判断错误） diag1[d1] = false; diag2[d2] = false; } } }