Kickstart - 2019 - Round A - Parcels

// currently editing

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> v(250,vector<int>(250,501)) // 250 is max c and r

vecto<pair<int,int>> dir{{-1,0},{0,-1},{0,1},{1,0}};

void bfs(int r, int c){

deque<pair<int,int>> q;

for (int i=0; i<r; ++i){

for (int j=0; j<c; ++j){

int a;

cin >> a;

if (a == 1){

q.push_back({i,j});

v[i][j]=0;

}

}

}

while (!q.empty()){

auto f=q.front();

int x=f.first,y=f.second;

q.pop_front();

for (auto& i:dir){

int nx=i.first+x,ny=y+i.second;

if (nx >= 0 and ny >= 0 and nx < r and ny < c){

if (v[nx][ny] > v[x][y]+1){

v[nx][ny]=v[x][y]+1;

q.push_back({nx,ny});

}

}

}

}

}

bool ok(int r, int c, int val){

for (){}

}

int bs(int r, int c){

int e=r+c,b=0; // Mahattan distance

while (b < e){

int mid=b+e;

if (ok(r,c,mid)) b=mid;

else e=mid;

}

return b; // or e;

}

int main(){

int T,id=0;

cin >> T;

while (T--){

int r,c;

cin >> r >> c;

bfs(r,c);

int ret=bs(r,c);

++id;

cout << "Case #" << id << ": " << ret << '\n';

}

return 0;

}