Description

你要在一个nxm的格子图上涂色,你每次可以选择一个未涂色的格子涂上你开始选定的那种颜色。同时为了美观,我们要求你涂色的格子不能相邻,也就是说,不能有公共边,现在问你,在采取最优策略的情况下,你最多能涂多少个格子?

给定格子图的长n和宽m。请返回最多能涂的格子数目。

测试样例:

1,2
返回:1

Solutions

1. Direct

# -*- coding:utf-8 -*-

class Paint:
    def getMost(self, n, m):
        prod = n * m 
        if prod % 2 == 0:
            return prod >> 1
        else:
            return (prod >> 1) + 1

References

  1. 13.1 方格涂色