你要在一个nxm的格子涂色图上涂色你每次可以选择一个未涂色的格子涂色涂上你开始选定的那种颜色。同时为了美观我们要求你涂色的格子涂色不能相邻,也就是说鈈能有公共边,现在问你在采取最优策略的情况下,你最多能涂多少个格子涂色
给定格子涂色图的长n和宽m。请返回最多能涂的格子涂銫数目
只有一种颜色,要想不相邻每行一个隔一个涂色即可,如果行数或者列数为偶数最多的格子涂色即为(m/2)*n或者(n/2)*m,显然就是m*n/2
如果行列均不为偶数假设多加一列,则最大格子涂色就为((n+1)/2)*m,然后需要减去多加的格子涂色数为(m-1)/2,两式合并即为(n*m+1)/2