Installing Firewalls

In a two-dimensional area of size n×m, you aim to install firewalls to minimize damage caused by fire. The fire spreads to all adjacent spaces in the up, down, left, and right directions, but it cannot penetrate through firewalls. For example, if the fire and firewalls are arranged as shown in [Figure 1], after the fire has spread completely, the state will change to that shown in [Figure 2].