fork(1) download
copy 
  1. //By Tushar Gautam
  2. #pragma GCC optimize ("-O2")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define all(x) x.begin(),x.end()
  11. #define memreset(a) memset(a,0,sizeof(a))
  12. #define testcase(t) int t;cin>>t;while(t--)
  13. #define forstl(i,v) for(auto &i: v)
  14. #define forn(i,e) for(int i = 0; i < e;++i)
  15. #define forsn(i,s,e) for(int i = s; i < e;++i)
  16. #define rforn(i,s) for(int i = s; i >= 0;--i)
  17. #define rforsn(i,s,e) for(int i = s; i >= e;--i)
  18. #define bitcount(a) __builtin_popcount(a) // set bits (add ll)
  19. #define ln '\n'
  20. #define getcurrtime ((double)clock()/CLOCKS_PER_SEC)
  21. #define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
  22. #define inputfile freopen("input.txt", "r", stdin)
  23. #define outputfile freopen("output.txt", "w", stdout)
  24. #define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
  25. stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  26. void err(istream_iterator<string> it) { cerr<<endl; }
  27. template<typename T, typename... Args>
  28. void err(istream_iterator<string> it, T a, Args... args) {
  29. 	cerr << *it << " = " << a << "\t"; err(++it, args...);
  30. }
  31. template<typename T1,typename T2>
  32. ostream& operator <<(ostream& c,pair<T1,T2> &v){
  33. 	c<<"("<<v.fi<<","<<v.se<<")"; return c;
  34. }
  35. template <template <class...> class TT, class ...T>
  36. ostream& operator<<(ostream& out,TT<T...>& c){
  37.     out<<"{ ";
  38.     forstl(x,c) out<<x<<" ";
  39.     out<<"}"; return out;
  40. }
  41. typedef long long ll;
  42. typedef unsigned long long ull;
  43. typedef long double ld;
  44. typedef pair<ll,ll> p64;
  45. typedef pair<int,int> p32;
  46. typedef pair<int,p32> p96;
  47. typedef vector<ll> v64;
  48. typedef vector<int> v32; 
  49. typedef vector<v32> vv32;
  50. typedef vector<v64> vv64;
  51. typedef vector<p32> vp32;
  52. typedef vector<p64> vp64;
  53. typedef vector<vp32> vvp32;
  54. typedef map<int,int> m32;
  55. const int LIM=1e5+5,MOD=1e9+7;
  56. int t,n,m,k,x,y,w;
  57. vector<string> in;
  58. vv32 d;
  59. bool valid(int i,int j,int di){
  60. 	return i<n && i>=0 && j<m && j>=0 && d[i][j]>di;
  61. }
  62. bool P(int k){
  63. 	int sm=MOD,sM=-MOD,dm=MOD,dM=-MOD;
  64. 	forn(i,n){
  65. 		forn(j,m){
  66. 			if(d[i][j]>k){
  67. 				sm=min(sm,i+j);
  68. 				sM=max(sM,i+j);
  69. 				dm=min(dm,i-j);
  70. 				dM=max(dM,i-j);
  71. 			}
  72. 		}
  73. 	}
  74. 	forn(i,n){
  75. 		forn(j,m){
  76. 			bool y=1;
  77. 			if(i+j+k<sM) y=0;
  78. 			if(i+j-k>sm) y=0;
  79. 			if(i-j+k<dM) y=0;
  80. 			if(i-j-k>dm) y=0;
  81. 			if(y) return 1;
  82. 		}
  83. 	}
  84. 	return 0;
  85. }
  86. void solve(int c){
  87. 	cin>>n>>m;
  88. 	in.resize(n);
  89. 	d.assign(n,v32(m,MOD));
  90. 	queue<p32> q;
  91. 	forn(i,n){
  92. 		cin>>in[i];
  93. 		forn(j,m){
  94. 			if(in[i][j]=='1') d[i][j]=0,q.push(mp(i,j));
  95. 		}
  96. 	}
  97. 	while(!q.empty()){
  98. 		auto tp=q.front(); q.pop();
  99. 		tie(x,y)=tp;
  100. 		int dd=d[tp.fi][tp.se];
  101. 		if(valid(x-1,y,1+dd)) d[x-1][y]=1+dd,q.push(mp(x-1,y));
  102. 		if(valid(x+1,y,1+dd)) d[x+1][y]=1+dd,q.push(mp(x+1,y));
  103. 		if(valid(x,y-1,1+dd)) d[x][y-1]=1+dd,q.push(mp(x,y-1));
  104. 		if(valid(x,y+1,1+dd)) d[x][y+1]=1+dd,q.push(mp(x,y+1));
  105. 	}
  106. 	int l=0,r=500;
  107. 	while(l<r){
  108. 		int mid=(l+r)/2;
  109. 		if(P(mid)) r=mid;
  110. 		else l=mid+1;
  111. 	}
  112. 	cout<<"Case #"<<c<<": "<<l<<ln;
  113. }
  114. signed main(){
  115. 	fastio;
  116. 	int c=0;
  117. 	testcase(tt) solve(++c);
  118. 	return 0;
  119. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
3 3
101
000
101
1 2
11
5 5
10001
00000
00000
00000
10001
stdout
copy 
Case #1: 1
Case #2: 0
Case #3: 2
https://ideone.com/uBTBJx
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!