kick start 2019 round A Parcels

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <list>
#include <limits.h>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

using namespace std;

vector<vector<int>> dis;
vector<pair<int,int>> office;
int max_dis;
vector<string> matrix;

/**
 * 多源BFS
 * 和单源BFS完全一致的写法就是，同一层level的先到先得，O(m*n)复杂度
 * matrix:输入的0-1矩阵  office为所有的源节点的坐标数组
 **/
int multiple_BFS(vector<string>& matrix,vector<pair<int,int>>& office) {
	queue<pair<int,int>> q;
	for(auto m : office) {
		q.push(m);
	}
	int level = 1;
	int res = 0;
	pair<int,int> last;
	if(!q.empty()) {
		last = q.back();
	}
	else {
		res = matrix.size()-1 + matrix[0].size()-1;
		dis = vector<vector<int>>(matrix.size(),vector<int>(matrix[0].size(),res));
		return res;
	}

	while(!q.empty()) {
		pair<int,int> cur = q.front();
		q.pop();
		int x = cur.first;
		int y = cur.second;
		res = max(res,dis[x][y]);
		if(x-1>=0 && dis[x-1][y]==-1) {
			dis[x-1][y] = level;
			q.push(make_pair(x-1,y));
		}
		if(x+1<matrix.size() && dis[x+1][y]==-1) {
			dis[x+1][y] = level;
			q.push(make_pair(x+1,y));
		}
		if(y-1>=0 && dis[x][y-1]==-1) {
			dis[x][y-1] = level;
			q.push(make_pair(x,y-1));
		}
		if(y+1<matrix[0].size() && dis[x][y+1]==-1) {
			dis[x][y+1] = level;
			q.push(make_pair(x,y+1));
		}
		if(cur == last) {
			++level;
			last = q.back();
		}
	}
	return res;
}

bool check(int max_dis,vector<vector<int>>& dis) {
	int m1 = INT_MIN, m2 = INT_MAX, m3 = INT_MIN, m4 = INT_MAX;

	for(int i=0;i<dis.size();++i) {
		for(int j=0;j<dis[0].size();++j) {
			if(dis[i][j]>max_dis) {
				m1 = max(m1,i+j);
				m2 = min(m2,i+j);
				m3 = max(m3,i-j);
				m4 = min(m4,i-j);
			}
		}
	}
	for(int i=0;i<dis.size();++i) {
		for(int j=0;j<dis[0].size();++j) {
			if(matrix[i][j]=='0') {
				int temp1 = max(abs(i+j-m1),abs(i+j-m2));
				int temp2 = max(abs(i-j-m3),abs(i-j-m4));
				if(max(temp1,temp2)<=max_dis)
					return true;
			}
		}
	}
	return false;
}

int binary_search(int max_dis,vector<vector<int>>& dis) {
	int l = 0,r = max_dis;
	while(l<r) {
		int mid = l + (r - l)/2;
		if(check(mid,dis)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l;
}

int main() {
    
	int T;
	cin >> T;

	for(int t=0;t<T;++t) {
        int res = 0;
		int R,C;
		cin >> R >> C;
		office = vector<pair<int,int>>();
		dis = vector<vector<int>>(R,vector<int>(C,-1));
		matrix = vector<string>(R,string());

		for(int i=0;i<R;++i) {
			cin >> matrix[i];
			for(int j=0;j<C;++j) {
				if(matrix[i][j]=='1') {
					office.push_back(make_pair(i,j));
					dis[i][j] = 0;
				}
			}
		}

		max_dis = multiple_BFS(matrix,office);

		res = binary_search(max_dis,dis);

		cout << "Case #" << t+1 << ":" << " " << res << endl; 
	}
    return 0;
}