public class GameOnABoard {
static public int[] dx = { 0, 1, 0, -1 };
static public int[] dy = { 1, 0, -1, 0 };
static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; }
struct Point { public int row, col, step;}
public int Solve(string[] cost, int si, int sj) {
int n = cost.Length;
int m = cost[0].Length;
Queue<Point> qu = new Queue<Point>();
Queue<Point> next = new Queue<Point>();
qu.Enqueue(new Point() { row = si, col = sj, step = cost[si][sj] == '1' ? 1 : 0 });
int farthest = 0;
bool[,] visited = new bool[n, m];
while (qu.Any() || next.Any()) {
while (qu.Any()) {
Point now = qu.Dequeue();
if (visited[now.row, now.col]) continue;
visited[now.row, now.col] = true;
farthest = Math.Max(farthest, now.step);
for (int k = 0; k < 4; k++) {
int nr = now.row + dy[k];
int nc = now.col + dx[k];
if (0 <= nr && nr < n && 0 <= nc && nc < m) {
if (!visited[nr, nc]) {
int add = (cost[nr][nc] == '1' ? 1 : 0);
if (add == 0)
qu.Enqueue(new Point() { row = nr, col = nc, step = now.step + add });
else
next.Enqueue(new Point() { row = nr, col = nc, step = now.step + add });
}
}
}
}
Swap(ref qu, ref next);
}
return farthest;
}
public int optimalChoice(string[] cost) {
int n = cost.Length;
int m = cost[0].Length;
int ans = int.MaxValue;
for (int si = 0; si < n; si++) {
for (int sj = 0; sj < m; sj++) {
ans = Math.Min(ans, Solve(cost, si, sj));
}
}
return ans;
}
}