蓝桥杯 (在矩阵中摆放最多的马相互不攻击)

2018年03月25日 11点热度 0人点赞 0条评论

蒜头君喜欢下棋。最近它迷上了国际象棋。国际象棋的棋盘可以被当做一个 8times 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 times 88×8 的棋盘上怎么放马,但如果棋盘变为 n times mn×m 的,蒜头君就不懂了。他希望你来帮忙他计算一下究竟能放多少匹马。

输入格式

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

输出格式

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

样例输入1

2 4

样例输出1

4

样例输入2

3 4

样例输出2

6

关于提示

蓝桥杯 (在矩阵中摆放最多的马相互不攻击)

当棋盘只有一行时,棋盘上全放上棋子即可。
当棋盘只有两行时,参考如下放的方法:
OOXXOOXXOO.....
OOXXOOXXOO.....
即放两排空两排。
其它情况下,参考国际象棋棋盘的颜色,马跳一次一定会从白色格子变为黑色,因此把所有马放在同一颜色下即可。

蓝桥杯 (在矩阵中摆放最多的马相互不攻击)

蓝桥杯 (在矩阵中摆放最多的马相互不攻击)

未经允许不得转载!蓝桥杯 (在矩阵中摆放最多的马相互不攻击)

update

纸上得来终觉浅, 绝知此事须躬行。