Minimum Walls to Contain a Spreading Region

You are given an m x n grid grid where grid[i][j] is 1 if that cell is affected and 0 if it is clear. A region is a group of affected cells joined 4-directionally.

Affected cells spread one step per round. Each round goes like this:

• Every region threatens the clear cells that sit 4-directionally beside it.
• You seal the region that threatens the most distinct clear cells. Sealing it means building one wall on each shared edge between one of its cells and a clear cell. A sealed region never spreads again, never joins another region, and its cells stay affected.
• Every other region then spreads: each clear cell it threatens becomes affected.

Rounds keep going until no region threatens a clear cell. You can assume that whenever some region still threatens a clear cell, exactly one region threatens more clear cells than every other region.

Return the total number of walls built.

Examples

Example 1

Input: grid = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]
Output: 10
Explanation: The region on the left threatens 5 clear cells and the one on the right threatens 4, so the left one is sealed with 5 walls and the right one spreads. In the next round only the right region is left, and sealing it takes 5 more walls.

Example 2

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 4
Explanation: The single region threatens only the middle cell, but that cell has an affected neighbor on all four sides, so sealing it takes 4 walls.

Example 3

Input: grid = [[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The long region on the right threatens more clear cells than the ring on the left, so it is sealed first with 11 walls. The ring then spreads into the one cell it encloses and into the column beside it, and sealing it in the next round takes 2 more walls.