import java.util.Scanner; public class Main { // 全局变量：行列、最大数、网格标记（零拷贝） 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]; // 行级DFS：从第0行开始，当前已放置0个 dfsRow(0, 0); System.out.println(max); } /** * 行级DFS核心：仅按行递归，递归深度=行数（最多10） * @param row 当前处理的行 * @param cur 当前已放置的传教士数量 */ private static void dfsRow(int row, int cur) { // 终极剪枝：无提升空间直接终止 int remain = n * m - row * m; if (cur + remain <= max) return; // 递归终止：遍历完所有行，更新最大值 if (row >= n) { if (cur > max) max = cur; return; } // 记录当前行处理前的状态（用于行级回溯） boolean[][] rowCopy = new boolean[1][m]; System.arraycopy(grid[row], 0, rowCopy[0], 0, m); // 记录当前行放置的数量 int add = 0; // 处理当前行的每一列：循环+即时放置/回溯 for (int col = 0; col < m; col++) { if (canPut(row, col)) { grid[row][col] = true; add++; // 每放置一个，立即尝试递归下一行（行级分支，压缩次数） dfsRow(row + 1, cur + add); } } // 情况1：当前行放了若干个，递归下一行 dfsRow(row + 1, cur + add); // 行级回溯：恢复当前行的原始状态 System.arraycopy(rowCopy[0], 0, grid[row], 0, m); // 情况2：当前行不放任何一个，递归下一行 dfsRow(row + 1, cur); } /** * 斜相邻冲突判断：仅4个方向，无冗余 */ private static boolean canPut(int i, int j) { if (i > 0 && j > 0 && grid[i-1][j-1]) return false; if (i > 0 && j < m-1 && grid[i-1][j+1]) return false; if (i < n-1 && j > 0 && grid[i+1][j-1]) return false; if (i < n-1 && j < m-1 && grid[i+1][j+1]) return false; return true; } }