GameOnABoard

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

Alice and Bob are playing a game on a rectangular board. We use (i, j) to denote the j-th cell in the i-th row (0-based index). Each cell has a cost of either 0 or 1 and they are given by the String[] cost. The j-th character of i-th element in cost (0-based index) denotes the cost of cell (i, j). A path between two distinct cells (x₁, y₁) and (x₂, y₂) is a sequence of cells (c₀, c₁, ..., c_k) such that c₀=(x₁, y₁), c_k=(x₂, y₂) and for each i from 0 to k-1, cells c_i and c_i+1 have a common side. Cost of a path is the total cost of cells on this path.

The game is played as follows: First Alice chooses a cell (x₁,y₁), then Bob chooses a cell (x₂,y₂) which is different from (x₁, y₁). Finally, they compute the value L: the minimum cost of a path between (x₁,y₁) and (x₂,y₂). Alice's goal is to minimize L, and Bob's goal is to maximize L. Compute and return the value L that will be achieved if both players play optimally.