#P1380. T型骨牌

T型骨牌

题目描述

现在要在 n×mn\times m 的棋盘上,摆入 T 型,T 型可以旋转,具体包括如下四个样式(“#”代表被T型占据的格子,“.”代表自由的格子):

###      ..#      .#.      #..
.#.      ###      .#.      ###
.#.      ..#      ###      #..
`

问最多能在 n×mn\times m 的棋盘上摆入多少个不重叠的 T 型。

输入格式

输入共一行两个数 n,mn,m

输出格式

输出共一个数,表示最多能放入多少个 T 型。

5 6

4

提示

数据范围及约定

对于全部数据,1n,m91\le n,m\le 9

样例说明