## 【二分】 Kickstart2019 Round A Problem B

### 传送门

#include<bits/stdc++.h>
using namespace std;
const int maxn = 255;
typedef pair<int,int> pii;
vector<pii> e;
int n,m;
int mp[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
void bfs(int k)
{
memset(vis, 0, sizeof vis);
queue<pair<int,pii> > q;
for(auto i : e) q.push({0, i}), vis[i.first][i.second] = 1;
while(q.size())
{
pii s = q.front().second;
int t = q.front().first;
q.pop();
if(t == k) continue;
int x = s.first, y = s.second;
for(int i = 0; i < 4; i++)
{
int dx = x + dir[i][0], dy = y + dir[i][1];
if(dx > 0 && dx <= n && dy > 0 && dy <= m && vis[dx][dy] == 0)
{
vis[dx][dy] = 1;
q.push({t + 1,{dx, dy}});
}
}
}
}
int dist(pii xxx, pii yyy)
{
int ax = xxx.first, ay = xxx.second, bx = yyy.first, by = yyy.second;
return max(abs(ax + ay - (bx + by)), abs(ax - ay - (bx - by)));
}
bool cmp1(const pii &x, const pii &y)
{
return x.first + x.second < y.first + y.second;
}
bool cmp2(const pii &x, const pii &y)
{
return x.first - x.second < y.first - y.second;
}
int main()
{
int T; cin >> T;
for(int cas = 1; cas <= T; cas++)
{
e.clear();
char s[maxn];
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
scanf("%s", s + 1);
for(int j = 1; j <= m; j++)
{
mp[i][j] = s[j] - '0';
if(mp[i][j]) e.push_back({i, j});
}
}
int l = 0, r = n + m;
while(l < r)
{
int mid = (l + r) >> 1;
bfs(mid);
vector<pii> a, b;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(vis[i][j] == 0)
{
a.push_back({i, j});
b.push_back({i, j});
}
}
sort(a.begin(), a.end(), cmp1);
sort(b.begin(), b.end(), cmp2);
int res = 0, flag = 1;
//cout<<a.size()<<endl;
if(a.size()) //这里被自己坑了半天
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
flag = 0;
if(mp[i][j] == 0)
{
flag = 0;
pii pp ;
pp.first = i; pp.second = j;
res = max(max(dist(a[0], pp), dist(a.back(), pp)),max(dist(b[0], pp), dist(b.back(), pp)));
if(res <= mid)
{
flag = 1;
break;
}
}
}
if(flag) break;
}
if(flag) r = mid;
else l = mid + 1;
}
//cout << l - 1 << endl;
printf("Case #%d: %d\n", cas, l);
}
}