import java.util.Scanner; // 严格遵守OJ要求：主类名Main，首字母大写，无其他字符 public class Main { // 全局变量：网格行列、最大放置数、对角线占用标记（仅行维度，更轻量） private static int n, m, maxCount = 0; private static boolean[] mainDiag; // 主对角线i-j，偏移10 private static boolean[] subDiag; // 副对角线i+j public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); // 题目输入：水平区域数（行） m = sc.nextInt(); // 题目输入：垂直区域数（列） sc.close(); // 初始化对角线数组，大小20足够覆盖10×10的所有情况（-9~9 → 1~19） mainDiag = new boolean[20]; subDiag = new boolean[20]; // 逐行DFS：从第0行开始，当前已放置0个 dfs(0, 0); // 仅输出结果，无任何多余字符（贴合OJ输出规范） System.out.println(maxCount); } /** * 极致优化的DFS：逐行处理，行内循环选列，大幅减少递归次数 * @param row 当前处理的行号（仅行维度递归，核心优化） * @param curCount 已放置的传教士数量 */ private static void dfs(int row, int curCount) { // 递归终止：遍历完所有行，更新最大值 if (row >= n) { if (curCount > maxCount) { maxCount = curCount; } return; } // 核心剪枝1：剩余行即使每行放1个，也超不过当前最大值，直接返回 // 剩余行 = n - row，理论最大可加 n - row，提前终止无效分支 if (curCount + (n - row) <= maxCount) { return; } // 处理当前行：遍历所有列，尝试在当前行的col列放置（或不放） // 先记录当前对角线状态（用于回溯整行），避免逐列回溯的冗余 boolean[] mainCopy = mainDiag.clone(); boolean[] subCopy = subDiag.clone(); // 情况1：当前行**不放**任何传教士，直接跳转到下一行 dfs(row + 1, curCount); // 情况2：当前行**放**传教士，遍历每一列尝试放置（无冲突则放） for (int col = 0; col < m; col++) { int d1 = row - col + 10; // 主对角线偏移，避免负数索引 int d2 = row + col; // 副对角线直接计算 // 冲突判断：当前列的对角线未被占用 if (!mainDiag[d1] && !subDiag[d2]) { // 标记对角线为占用 mainDiag[d1] = true; subDiag[d2] = true; // 递归下一行，数量+1（当前行放1个，逐列尝试） dfs(row + 1, curCount + 1); // 回溯：恢复当前行的对角线状态（整行克隆恢复，比逐列恢复更快） mainDiag = mainCopy.clone(); subDiag = subCopy.clone(); } } } }