Tree Planting on a Grid (no adjacent trees)

You are given an m x n land grid named grid: A value of 1 indicates a tree that is already planted. A value of 0 identifies an unoccupied cell. You can add trees only to vacant cells, while observing these conditions: Any pair of trees, whether pre-existing or added, must not share an edge. Diagonal contact is allowed. Determine the largest number of trees that can be added. Input (stdin): Line 1 contains m n. The following m lines each contain n values, where every value is…