import java.util.Scanner; // 在线测评强制主类名Main public class Main { // 全局变量：记录最大传教士数量、国土的行列数 private static int maxNum = 0; private static int n, m; // 标记主对角线(i-j)、副对角线(i+j)是否被占用（有传教士） private static boolean[] mainDiag; // 主对角线：i-j，范围[-9,9]，偏移10转为[0,18] private static boolean[] subDiag; // 副对角线：i+j，范围[0,18]（n,m<=10，最大i+j=9+9=18） public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 水平区域数（行） m = sc.nextInt(); // 垂直区域数（列） sc.close(); // 初始化对角线标记数组，处理主对角线的负数偏移 int diagLen = 2 * Math.max(n, m) - 1; mainDiag = new boolean[20]; // 偏移10，足够容纳[-9,9] subDiag = new boolean[20]; // 足够容纳[0,18] // 从第0行第0列开始DFS，当前已放置数量为0 dfs(0, 0, 0); // 输出最大数量 System.out.println(maxNum); } /** * 深度优先搜索核心方法 * @param i 当前遍历的行 * @param j 当前遍历的列 * @param curNum 已放置的传教士数量 */ private static void dfs(int i, int j, int curNum) { // 递归终止条件：遍历完所有行，更新最大数量 if (i >= n) { if (curNum > maxNum) { maxNum = curNum; } return; } // 处理列的换行：当前列遍历完，进入下一行第0列 int nextI = i; int nextJ = j + 1; if (nextJ >= m) { nextI = i + 1; nextJ = 0; } // 选择1：不放置传教士，直接遍历下一个格子 dfs(nextI, nextJ, curNum); // 选择2：放置传教士（判断是否无冲突） // 主对角线偏移10，将负数转为正数（如0-9=-9 → 1） int mainKey = i - j + 10; int subKey = i + j; if (!mainDiag[mainKey] && !subDiag[subKey]) { // 标记对角线为占用 mainDiag[mainKey] = true; subDiag[subKey] = true; // 递归遍历下一个格子，已放置数量+1 dfs(nextI, nextJ, curNum + 1); // 回溯：恢复对角线标记（关键！DFS必须回溯） mainDiag[mainKey] = false; subDiag[subKey] = false; } } }