There is a rectangle garden in front of Gina’s house. The garden can be seen as an n-by-m rectangular grid. All grid cells are identical squares, and two grid cells are considered adjacent if they share an common edge. Gina loves cacti and wants to plant as many cacti as possible in the garden. However, there are some constraints on planting cacti. The soil can be too wet in some of the cells and therefore is not suitable for cacti. Gina cannot plant cacti in those cells. Since the soil in each cell is not fertile enough to grow two or more cacti, Gina may plant at most one cactus in a cell. At most one cactus can be planted in any pair of adjacent cells. Otherwise, the cacti in those cells may be harmed by their neighbor’s thorns. Please write a program to help Gina calculate the maximum possible number of cacti can be planted, and also a way of plantings that meet the listed constraints.
There is a rectangle garden in front of Gina’s house. The garden can be seen as an n-by-m rectangular grid. All grid cells are identical squares, and two grid cells are considered adjacent if they share an common edge. Gina loves cacti and wants to plant as many cacti as possible in the garden. However, there are some constraints on planting cacti. • The soil can be too wet in some of the cells and therefore is not suitable for cacti. Gina cannot plant cacti in those cells. • Since the soil in each cell is not fertile enough to grow two or more cacti, Gina may plant at most one cactus in a cell. • At most one cactus can be planted in any pair of adjacent cells. Otherwise, the cacti in those cells may be harmed by their neighbor’s thorns. Please write a program to help Gina calculate the maximum possible number of cacti can be planted, and also a way of plantings that meet the listed constraints.
