#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template < class S, class T> inline S chmax( S & a, T b) {
if ( a< b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
int x;
int y;
int dist[ 100 ] [ 100 ] ;
int q[ 10000 ] ;
int qs;
int qe;
class Solution{
public :
int maxDistance( vector< vector< int >> & A) {
int d, di[ 4 ] = { - 1 ,1 ,0 ,0 } , dj[ 4 ] = { 0 ,0 ,- 1 ,1 } , i, j, k, ni, nj, res= 0 , si, sj;
x = A.size ( ) ;
y = A[ 0 ] .size ( ) ;
for ( i= 0 ; i< ( x) ; i++ ) {
for ( j= 0 ; j< ( y) ; j++ ) {
dist[ i] [ j] = - 1 ;
}
}
qs = qe = 0 ;
for ( i= 0 ; i< ( x) ; i++ ) {
for ( j= 0 ; j< ( y) ; j++ ) {
if ( A[ i] [ j] == 1 ) {
dist[ i] [ j] = 0 ;
q[ qe++ ] = i* y+ j;
}
}
}
while ( qs < qe) {
k = q[ qs++ ] ;
si = k / y;
sj = k % y;
for ( d= 0 ; d< ( 4 ) ; d++ ) {
ni = si + di[ d] ;
nj = sj + dj[ d] ;
if ( ni < 0 || nj < 0 || ni >= x || nj >= y || dist[ ni] [ nj] >= 0 ) {
continue ;
}
dist[ ni] [ nj] = dist[ si] [ sj] + 1 ;
q[ qe++ ] = ni * y + nj;
}
}
for ( i= 0 ; i< ( x) ; i++ ) {
for ( j= 0 ; j< ( y) ; j++ ) {
chmax( res, dist[ i] [ j] ) ;
}
}
if ( res== 0 ) {
res = - 1 ;
}
return res;
}
}
;
// cLay varsion 20190820-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int x, y;
// int dist[100][100];
// int q[10000], qs, qe;
//
// class Solution {
// public:
// int maxDistance(vector<vector<int>>& A) {
// int i, j, k;
// int di[4] = {-1,1,0,0}, dj[4] = {0,0,-1,1}, d, si, sj, ni, nj;
// int res = 0;
//
// x = A.size();
// y = A[0].size();
//
// rep(i,x) rep(j,y) dist[i][j] = -1;
// qs = qe = 0;
//
// rep(i,x) rep(j,y) if(A[i][j]==1){
// dist[i][j] = 0;
// q[qe++] = i*y+j;
// }
// while(qs < qe){
// k = q[qs++];
// si = k / y;
// sj = k % y;
// rep(d,4){
// ni = si + di[d];
// nj = sj + dj[d];
// if(ni < 0 || nj < 0 || ni >= x || nj >= y || dist[ni][nj]>=0) continue;
// dist[ni][nj] = dist[si][sj] + 1;
// q[qe++] = ni * y + nj;
// }
// }
//
// rep(i,x) rep(j,y) res >?= dist[i][j];
// if(res==0) res = -1;
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBTIGNobWF4KFMgJmEsIFQgYil7CiAgaWYoYTxiKXsKICAgIGE9YjsKICB9CiAgcmV0dXJuIGE7Cn0KI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICByZXR1cm4gMDsKfQojdW5kZWYgbWFpbgppbnQgeDsKaW50IHk7CmludCBkaXN0WzEwMF1bMTAwXTsKaW50IHFbMTAwMDBdOwppbnQgcXM7CmludCBxZTsKY2xhc3MgU29sdXRpb257CiAgcHVibGljOgogIGludCBtYXhEaXN0YW5jZSh2ZWN0b3I8dmVjdG9yPGludD4+JiBBKXsKICAgIGludCBkLCBkaVs0XT17LTEsMSwwLDB9LCBkals0XT17MCwwLC0xLDF9LCBpLCBqLCBrLCBuaSwgbmosIHJlcz0wLCBzaSwgc2o7CiAgICB4ID0gQS5zaXplKCk7CiAgICB5ID0gQVswXS5zaXplKCk7CiAgICBmb3IoaT0wO2k8KHgpO2krKyl7CiAgICAgIGZvcihqPTA7ajwoeSk7aisrKXsKICAgICAgICBkaXN0W2ldW2pdID0gLTE7CiAgICAgIH0KICAgIH0KICAgIHFzID0gcWUgPSAwOwogICAgZm9yKGk9MDtpPCh4KTtpKyspewogICAgICBmb3Ioaj0wO2o8KHkpO2orKyl7CiAgICAgICAgaWYoQVtpXVtqXT09MSl7CiAgICAgICAgICBkaXN0W2ldW2pdID0gMDsKICAgICAgICAgIHFbcWUrK10gPSBpKnkrajsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIHdoaWxlKHFzIDwgcWUpewogICAgICBrID0gcVtxcysrXTsKICAgICAgc2kgPSBrIC8geTsKICAgICAgc2ogPSBrICUgeTsKICAgICAgZm9yKGQ9MDtkPCg0KTtkKyspewogICAgICAgIG5pID0gc2kgKyBkaVtkXTsKICAgICAgICBuaiA9IHNqICsgZGpbZF07CiAgICAgICAgaWYobmkgPCAwIHx8IG5qIDwgMCB8fCBuaSA+PSB4IHx8IG5qID49IHkgfHwgZGlzdFtuaV1bbmpdPj0wKXsKICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICBkaXN0W25pXVtual0gPSBkaXN0W3NpXVtzal0gKyAxOwogICAgICAgIHFbcWUrK10gPSBuaSAqIHkgKyBuajsKICAgICAgfQogICAgfQogICAgZm9yKGk9MDtpPCh4KTtpKyspewogICAgICBmb3Ioaj0wO2o8KHkpO2orKyl7CiAgICAgICAgY2htYXgocmVzLCBkaXN0W2ldW2pdKTsKICAgICAgfQogICAgfQogICAgaWYocmVzPT0wKXsKICAgICAgcmVzID0gLTE7CiAgICB9CiAgICByZXR1cm4gcmVzOwogIH0KfQo7Ci8vIGNMYXkgdmFyc2lvbiAyMDE5MDgyMC0xCgovLyAtLS0gb3JpZ2luYWwgY29kZSAtLS0KLy8gI2RlZmluZSBtYWluIGR1bW15X21haW4KLy8ge30KLy8gI3VuZGVmIG1haW4KLy8gCi8vIGludCB4LCB5OwovLyBpbnQgZGlzdFsxMDBdWzEwMF07Ci8vIGludCBxWzEwMDAwXSwgcXMsIHFlOwovLyAKLy8gY2xhc3MgU29sdXRpb24gewovLyBwdWJsaWM6Ci8vICAgaW50IG1heERpc3RhbmNlKHZlY3Rvcjx2ZWN0b3I8aW50Pj4mIEEpIHsKLy8gICAgIGludCBpLCBqLCBrOwovLyAgICAgaW50IGRpWzRdID0gey0xLDEsMCwwfSwgZGpbNF0gPSB7MCwwLC0xLDF9LCBkLCBzaSwgc2osIG5pLCBuajsKLy8gICAgIGludCByZXMgPSAwOwovLyAKLy8gICAgIHggPSBBLnNpemUoKTsKLy8gICAgIHkgPSBBWzBdLnNpemUoKTsKLy8gCi8vICAgICByZXAoaSx4KSByZXAoaix5KSBkaXN0W2ldW2pdID0gLTE7Ci8vICAgICBxcyA9IHFlID0gMDsKLy8gCi8vICAgICByZXAoaSx4KSByZXAoaix5KSBpZihBW2ldW2pdPT0xKXsKLy8gICAgICAgZGlzdFtpXVtqXSA9IDA7Ci8vICAgICAgIHFbcWUrK10gPSBpKnkrajsKLy8gICAgIH0KLy8gICAgIHdoaWxlKHFzIDwgcWUpewovLyAgICAgICBrID0gcVtxcysrXTsKLy8gICAgICAgc2kgPSBrIC8geTsKLy8gICAgICAgc2ogPSBrICUgeTsKLy8gICAgICAgcmVwKGQsNCl7Ci8vICAgICAgICAgbmkgPSBzaSArIGRpW2RdOwovLyAgICAgICAgIG5qID0gc2ogKyBkaltkXTsKLy8gICAgICAgICBpZihuaSA8IDAgfHwgbmogPCAwIHx8IG5pID49IHggfHwgbmogPj0geSB8fCBkaXN0W25pXVtual0+PTApIGNvbnRpbnVlOwovLyAgICAgICAgIGRpc3RbbmldW25qXSA9IGRpc3Rbc2ldW3NqXSArIDE7Ci8vICAgICAgICAgcVtxZSsrXSA9IG5pICogeSArIG5qOwovLyAgICAgICB9Ci8vICAgICB9Ci8vIAovLyAgICAgcmVwKGkseCkgcmVwKGoseSkgcmVzID4/PSBkaXN0W2ldW2pdOwovLyAgICAgaWYocmVzPT0wKSByZXMgPSAtMTsKLy8gICAgIHJldHVybiByZXM7Ci8vICAgfQovLyB9Owo=