当前位置: 首页 > >

计蒜客 2018蓝桥杯省赛 B组模拟赛(五) H题 蒜头君下棋(java)

发布时间:



蒜头君下棋




蒜头君喜欢下棋。最*它迷上了国际象棋。国际象棋的棋盘可以被当做一个?8 imes 88×8?的矩阵,棋子被放在格子里面(不是和中国象棋一样放在线上)。


蒜头君特别喜欢国际象棋里面的马,马的移动规则是这样的:横着走两步之后竖着走一步,或者横着走一步之后竖着走两步。例如,一匹马在?(3,3)(3,3)?的位置,则它可以到达的地方有?(1,2)(1,2),(2,1)(2,1),(1,4)(1,4),(4,1)(4,1),(5,2)(5,2),(2,5)(2,5),(5,4)(5,4),(4,5)(4,5)?八个地方。蒜头君想要把整个棋盘都放上马,并且让这些马不能相互攻击(即任何一匹马不能走一步之后就到达另一匹马的位置)。蒜头君当然知道在?8 imes 88×8?的棋盘上怎么放马,但如果棋盘变为?n imes mn×m?的,蒜头君就不懂了。他希望你来帮忙他计算一下究竟能放多少匹马。


输入格式

共一行,两个整数nn和mm(1 leq n , m leq 10001≤n,m≤1000),代表棋盘一共有?nn?行?mm列。


输出格式

输出一个整数,代表棋盘上最多能放的马的数量。





样例输入1

2 4


样例输出1

4


样例输入2

3 4


样例输出2

6







思路:


用sum表示可以放的最多的棋子个数


若n>m先将m和n调换位置,我们按照行数多的进行解题。


(1)当棋盘只有一行时,棋盘上全放上棋子即可,即sum=m。


(2)当棋盘只有两行时,参考如下放的方法:


OOXXOOXXOO.....


OOXXOOXXOO.....


即放两排空两排。


如图当n=2时 m与sum 的关系




可以找到规律:当m除4取余结果为0时 sum=m;


? ? ? ? ? ? ? ? ? ? ??当m除4取余结果为1时 sum=m+1;


? ? ? ? ? ? ? ? ? ? ? 否则sum=m / 4 * 4 + 4;


(3)其它情况下,参考国际象棋棋盘的颜色,马跳一次一定会从白色格子变为黑色,因此把所有马放在同一颜色下即可。




根据图中黑色和白色位置关系可以得出规律:sum = (n * m + 1) / 2;






代码如下:


import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int sum = 0;
if(n>m){
int t = n;
n = m;
m = t;
}
if (n==1)
sum=m;
else if(n==2){
if(m%4==0){
sum=m;
}
else if(m%4==1){
sum=m+1;
}else{
sum=m/4*4+4;
}
}else{
sum=(n*m+1)/2;
}
System.out.println(sum);
}

}


https://blog.csdn.net/mcp3128/article/details/79704114





友情链接: