Grid Color Propagation Connectivity

Given a grid of size \(n \times m\) where each cell is colored either black or white, you can perform a series of operations. In one operation, you must choose one of the four directions: up, down, left or right. Then, for every black cell that is not on the boundary in the chosen direction, the adjacent cell in that direction becomes black. The initial set of black cells remains black. Note that the propagation from each black cell happens simultaneously.

The goal is to determine the minimum number of operations required so that all black cells become 8-connected (that is, for any two black cells, there exists a path of black cells where consecutive cells share at least one common vertex). In other words, the final set of black cells should form a single connected component under 8-neighbor connectivity.

Observation and Hint: Let the initial black cells have row indices with minimum \(r_{min}\) and maximum \(r_{max}\) and column indices with minimum \(c_{min}\) and maximum \(c_{max}\). One may show that an optimal strategy is to extend the regions from the extreme black cells so as to “bridge” the vertical gap \(\Delta r = r_{max}-r_{min}\) and the horizontal gap \(\Delta c = c_{max}-c_{min}\). When only one row (or one column) is involved (i.e. one gap is zero) the minimum operations needed is \(\max(\Delta r,\Delta c)-1\). Otherwise, if both gaps are positive, then the minimum operations required is \(\Delta r+\Delta c-2\).

It is guaranteed that the grid has at least one black cell. (A single black cell is trivially 8-connected.)

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns, respectively). The next \(n\) lines each contain a string of length \(m\) consisting only of characters 'B' (black) and 'W' (white), representing the grid.

outputFormat

Output a single integer representing the minimum number of operations required to make all black cells 8-connected.

sample

3 3
BWW
WWW
WWB

2