UVa 696 How Many Knights

题目描述

在国际象棋中，骑士（马）的攻击方式为：水平移动222格、垂直移动111格，或水平移动111格、垂直移动222格。给定一个M×NM \times NM×N的棋盘（M,N≤500M, N \le 500M,N≤500），求最多能放置多少个骑士，使得任意两个骑士互不攻击。

输入格式

多组数据，每行两个整数MMM和NNN，以0 0结束。

输出格式

对于每组数据，输出一行，格式为：

X knights may be placed on a M row N column board.

其中XXX为最大骑士数。

样例

输入

2 3 5 5 4 7 0 0

输出

4 knights may be placed on a 2 row 3 column board. 13 knights may be placed on a 5 row 5 column board. 14 knights may be placed on a 4 row 7 column board.

题目分析

本题是经典的“棋盘上放置骑士”问题。骑士的攻击关系构成一个二分图（骑士只攻击异色格），因此最大独立集 = 总格数 - 最大匹配数。但由于棋盘可达500×500500 \times 500500×500，二分图匹配不可行。但本题有更简单的数学规律：

  • 若M>NM > NM>N，交换MMM和NNN，使M≤NM \le NM≤N。
  • 若M=1M = 1M=1：可以放满所有格子，即NNN。
  • 若M=2M = 2M=2：每444列可放444个（两行各222个），剩余列按规律放置。
  • 若M≥3M \ge 3M≥3：可以放置⌈M×N2⌉\lceil \frac{M \times N}{2} \rceil⌈2M×N​⌉个（即所有格子的一半，上取整），因为可以按棋盘染色，所有同色格互不攻击（骑士攻击异色格）。

但注意当M=3M = 3M=3且NNN较小时，规律略有不同，但上述公式仍适用。

解题思路

  1. 若M>NM > NM>N，交换MMM和NNN。
  2. 若M=1M = 1M=1，答案=N= N=N。
  3. 若M=2M = 2M=2，答案=4×⌊N/4⌋+2×min⁡(N mod 4,2)= 4 \times \lfloor N/4 \rfloor + 2 \times \min(N \bmod 4, 2)=4×⌊N/4⌋+2×min(Nmod4,2)。
  4. 否则，答案=⌈M×N2⌉= \lceil \frac{M \times N}{2} \rceil=⌈2M×N​⌉。

复杂度分析

  • O(1)O(1)O(1)时间。

代码实现

// How Many Knights// UVa ID: 696// Verdict: Accepted// Submission Date: 2016-08-25// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intm,n;while(cin>>m>>n){if(m==0&&n==0)break;intmaxCounter=0;if(m==0||n==0)maxCounter=0;elseif(m==1||n==1)maxCounter=max(m,n);elseif(m==2||n==2){intnext_m=max(m,n);maxCounter=next_m/4*4;next_m=next_m%4;if(next_m>2)next_m=2;maxCounter+=next_m*2;}elseif(m==3||n==3){intnext_m=max(m,n);maxCounter=next_m/2*3;if(next_m%2==1)maxCounter+=2;}else{introw_counter=0,column_counter=0;if(m%2==1){row_counter=n/2*m;if(n%2==1)row_counter+=(m+1)/2;}elserow_counter=n*((m+1)/2);if(n%2==1){column_counter=m/2*n;if(m%2==1)column_counter+=(n+1)/2;}elsecolumn_counter=m*((n+1)/2);maxCounter=max(row_counter,column_counter);}cout<<maxCounter<<" knights may be placed on a "<<m<<" row "<<n<<" column board.\n";}return0;}

总结

本题通过分类讨论得出骑士最大放置数的公式。关键点包括：

  • 对于M=1M=1M=1或M=2M=2M=2的特殊处理。
  • 对于M≥3M \ge 3M≥3，利用棋盘染色性质，最多放置一半格子（上取整）。
  • 注意MMM和NNN可以互换。

该解法是棋盘放置问题的经典结论，适合作为数学规律题练习。