696 - How Many Knights(數論)

696 - How Many Knights(數論)

696 - How Many Knights(數論)

題目鏈接

題目大意：要求在一個棋盤上放上最多的騎士，但他們之間不能互相攻擊。騎士的攻擊范圍題目中有圖給出。

思路：畫到後面會發現上下兩行騎士交錯的放是最優的策略
(N N N)
( N N )
(N N N)
但是這個只適用與3*3矩陣和更大的矩陣，小點的就要另外討論了。
一行或者一列的時後每個位置都是可以放的，不會互相攻擊。兩行的時候就需要前面兩列，放四個騎士，後面接著的兩列就不能放，然後再繼續往後放，所以就是四列四列的進行考慮。

代碼：

#include 
#include 
#include 

using namespace std;

int main () {

    int n, m, r, c, ans;
    while (scanf ("%d%d", &n, &m) && (n || m)) {

        r = min(n, m);
        c = max(n, m);

        if (r == 2) {
            int mod = c % 4;
            int mul = c / 4;
            ans = mul * 4 + (mod <= 2? (mod * 2) : 4); 
        } else if (r <= 1) {
            ans = r * c;
        } else {
            ans = （n * m + 1) / 2; 
        }

        printf ("%d knights may be placed on a %d row %d column board.\n", ans, n, m);
    }
    return 0;
}