import java.util.Scanner; // 强制主类名Main，无任何修改 public class Main { // 全局变量：网格行列、最大放置数、网格放置标记（true=已放） private static int n, m, max = 0; private static boolean[][] grid; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 行（水平区域数） m = sc.nextInt(); // 列（垂直区域数） sc.close(); grid = new boolean[n][m]; // 初始化放置标记，默认false dfs(0, 0, 0); // 从(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 remain = n * m - (i * m + j); if (cnt + remain <= 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：当前格子放，判断【4个斜相邻】是否无据点（核心正确规则） if (canPut(i, j)) { grid[i][j] = true; // 标记放置 dfs(ni, nj, cnt + 1); // 递归下一个格子，数量+1 grid[i][j] = false; // 回溯：取消标记（DFS必备） } } /** * 关键方法：判断格子(i,j)是否可以放置（4个斜相邻无据点） * @param i 行 * @param j 列 * @return 可放置返回true，否则false */ private static boolean canPut(int i, int j) { // 检查4个斜相邻位置：上左、上右、下左、下右 // 先判断坐标是否越界，再判断是否已放置 if (i > 0 && j > 0 && grid[i-1][j-1]) return false; // 上左(i-1,j-1) if (i > 0 && j < m-1 && grid[i-1][j+1]) return false; // 上右(i-1,j+1) if (i < n-1 && j > 0 && grid[i+1][j-1]) return false; // 下左(i+1,j-1) if (i < n-1 && j < m-1 && grid[i+1][j+1]) return false; // 下右(i+1,j+1) return true; // 无斜相邻据点，可放置 } }