SCAU ACM TEAM寒假习题C---Knights in Chessboard

逃离我推掉我的手 2023-06-30 01:51 19阅读 0赞

## 题目介绍 ##

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.  
![在这里插入图片描述][format_png]  
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  
3

8 8

3 7

4 10

Sample Output  
Case 1: 32

Case 2: 11

Case 3: 20

## 大致说下我自己的解题思路和方法吧。 ##

具题目给出的图可以看出来（通过平移马）马全在褐色或黄色格子上是最多。  
所以对于行列都大于3的数来说，它的答案就为褐色和黄色格子中数目最多的那个。对于行列其中一个等于1的情况来说，它的答案就算非1的行或列的数。对于行或列其中一个为2的情况来说，可以发现如下规律。  
第一行: O O X X O O X X O O X X \[ \] \[ \]  
第二行: O O X X O O X X O O X X \[ \] \[ \];  
不难发现每两个差必有两个圆，最后两个括号填什么也就不用我说了，规律如此。  
所以它的周期为4，每4次有一个循环。  
所以如果n(行或列，不为2的数)%4<2，它的答案就是(n/4)\*4+(n%4)\*2；  
若n%4>=2,则答案为(n/4)\*4+4;

以上是我的解释，下面是代码

#include <iostream>
    #include<cstdio>
    using namespace std;
    int main()
    {
        
        int T,Case=1;
        cin>>T;
        while(T--)
        {
        
            int m,n,total;
            cin>>m>>n;
            total=m*n;
            if(n==1||m==1) printf("Case %d: %d\n",Case,total);
           else if(total&1) printf("Case %d: %d\n",Case,total/2+1);
           else if(n== 2||m== 2)
            {
        
                if(n==2) swap(m,n);
                if(m==2)
                {
        
                    if(n%4<2) printf("Case %d: %d\n",Case,(n/4)*4+(n%4)*2);
                    else printf("Case %d: %d\n",Case,(n/4)*4+4);
                }
            }
        else printf("Case %d: %d\n",Case,total/2);
            Case++;
        }
        return 0;
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly92ai56MTgwLmNuL2E2NDNiYTlkNGYyYjk5ZThkYTY4ZDg1YzRkNjZjYTdl?x-oss-process=image/format,png