| Time Limit: 1 second(s) | Memory Limit: 32 MB |
Given an m x n chessboard where you want to place chess knights. You have to find the number of maximum knights that can be placed in the chessboard such that no two knights attack each other.
Those who are not familiar with chess knights, note that a chess knight can attack 8 positions in the board as shown in the picture below.
Input
Input starts with an integer T (≤ 41000), denoting the number of test cases.
Each case contains two integers m, n (1 ≤ m, n ≤ 200). Here m and n corresponds to the number of rows and the number of columns of the board respectively.
Output
For each case, print the case number and maximum number of knights that can be placed in the board considering the above restrictions.
Sample Input |
Output for Sample Input |
|
3 8 8 3 7 4 10 |
Case 1: 32 Case 2: 11 Case 3: 20 |
首先考虑只有一行的时候，因为马要跳行（列）攻击，所以同属于一行（列）的肯定可以放满。
再就是有两行（列）的情况，可以发现这样一个特点，如果前一个2*2的格子放满棋子之后，后面接着的2*2的格子全都变成了无效的位置。现在的问题是这种方法是不是最优的情况。以2*3的棋盘为例，会发生冲突的位置有开始和结尾，只要一个位置放置了棋子，相应的位置就会减少一个，并且这种减少是不可避免的。同样的，对于一个2*n的棋盘，从前往后进行，每一列都有对应有冲突的一列，只能放一处，所以这种策略是没有问题的。
最后是n*m（n>2, m > 2）,可以发现，每一个棋子对应着8个攻击的位置，同样的，每一个攻击位置也对应着8个棋子的位置，从这里可以看出，这两个是等价的，所以棋子与攻击的位置应该有相同的数量。现在但是当n和m同时为奇数的时候，会有最后一个位置留给最后一个棋子。
#include <map> #include <set> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <iostream> #include <stack> #include <cmath> #include <string> #include <vector> #include <cstdlib> //#include <bits/stdc++.h> //#define LOACL #define space " " using namespace std; //typedef long long Long; //typedef __int64 Int; typedef pair<int, int> paii; const int INF = 0x3f3f3f3f; const double ESP = 1e-5; const double PI = acos(-1.0); const int MOD = 1e9 + 7; const int MAXN = 1e5; int main() { int t, ans, m, n; int Kcase = 0; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); if (n == 1 || m == 1) ans = n*m; else if (n == 2 || m == 2) { m = max(n, m); ans = m/4*4; if (m % 4 == 1) ans += 2; else if (m % 4 > 1) ans += 4; } else { if (n*m % 2 == 0) ans = m*n/2; else ans = m*n/2 + 1; } printf("Case %d: %d ", ++Kcase, ans); } return 0; }