A virus is spreading across an $m \times n$ grid given by isInfected, where:

• isInfected[i][j] = 0 represents an uncontaminated cell.

• isInfected[i][j] = 1 represents an infected cell.

A viral region consists of infected cells that are connected $4$ directionally (up, down, left, right).

Every day, the following steps occur in order:

• The viral region that threatens to contaminate the strictly greatest number of uninfected cells in the upcoming round is quarantined. You build walls along every boundary between infected cells in this region and their adjacent uninfected cells. Once quarantined, this region cannot spread, and its cells can no longer threaten any neighbors.

• Every remaining active viral region spreads to all adjacent uninfected cells ($4$ directionally).

This daily process continues until no new cells can be infected or all viral regions are quarantined.

Return the total number of walls built to contain the virus.

Constraints:

• m $==$ isInfected.length

• n $==$ isInfected[i].length

• $1 \leq$ m, n $\leq 50$

• isInfected[i][j] is either $0$ or $1$.

• There is always a contiguous viral region throughout the described process that will infect strictly more uncontaminated squares in the next round.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.