import java.util.Scanner; import java.util.Stack; public class Main { // 栈中仅存关键状态：行、列、已放数量、是否已处理过（用于回溯标记） static class Node { int i, j, cnt; boolean isProcessed; Node(int i, int j, int cnt, boolean isProcessed) { this.i = i; this.j = j; this.cnt = cnt; this.isProcessed = isProcessed; } } private static int n, m, maxCnt = 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]; Stack<Node> stack = new Stack<>(); // 初始状态：(0,0)，已放0个，未处理 stack.push(new Node(0, 0, 0, false)); while (!stack.isEmpty()) { Node node = stack.pop(); int i = node.i, j = node.j, cnt = node.cnt; boolean processed = node.isProcessed; // 终极剪枝：剩余格子+当前数 ≤ 最大值，直接跳过 int remain = n * m - (i * m + j); if (cnt + remain <= maxCnt) continue; // 递归终止：遍历完所有行，更新最大值 if (i >= n) { if (cnt > maxCnt) maxCnt = cnt; continue; } // 处理换行：当前列越界则跳转到下一行第0列 int nextI = i, nextJ = j + 1; if (nextJ >= m) { nextI = i + 1; nextJ = 0; } if (!processed) { // 第一次弹出：未处理，先入栈【不放置】的状态（后执行） stack.push(new Node(nextI, nextJ, cnt, false)); // 再判断是否可放置，可放置则入栈【放置】的预处理状态+标记当前为已处理 if (canPut(i, j)) { grid[i][j] = true; // 标记放置 stack.push(new Node(i, j, cnt, true)); // 已处理状态（用于回溯） stack.push(new Node(nextI, nextJ, cnt + 1, false)); // 放置后的下一个状态 } } else { // 第二次弹出：已处理，回溯恢复格子状态（仅放置过的才需要） grid[i][j] = false; } } System.out.println(maxCnt); } // 严格的斜相邻冲突判断（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; } }