fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x)	scanf("%d",&x)
  8. #define sl(x)	scanf("%lld",&x)
  9. #define ss(s)	scanf("%s",s)
  10. #define pi(x)	prllf("%d\n",x)
  11. #define pl(x)	prllf("%lld\n",x)
  12. #define ps(s)	prllf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<ll, ll>	pii;
  23. typedef pair<ll, ll>	pll;
  24. typedef vector<ll>		vi;
  25. typedef vector<ll>		vll;
  26. typedef vector<pii>		vpii;
  27. typedef vector<pll>		vpll;
  28. typedef vector<vi>		vvi;
  29. typedef vector<vll>		vvl;
  30. const ll mod = 1000000007;
  31.  
  32. const ll N = 1003;
  33. vi g[N];
  34. ll a[N][N], dp[N][N];
  35. ll dx[] = {+1, +1, +1, -1, -1, -1, +0, +0};
  36. ll dy[] = {-1, +1, +0, -1, +1, +0, +1, -1};
  37. ll n, m;
  38. ll vis[N][N], x1, Y1, x2, y2, T;
  39. bool val(ll x, ll y){
  40. 	return x<=n and y<=m and x>=1 and y>=1;
  41. }
  42. void fill(ll x, ll y){
  43. 	vis[x][y] = 1;
  44. 	ll i;
  45. 	fo(i, 8){
  46. 		ll nx = x+dx[i];
  47. 		ll ny = y+dy[i];
  48. 		if(!val(nx, ny) or vis[nx][ny] or a[nx][ny] != 1) continue;
  49. 		fill(nx, ny);
  50. 	}
  51. }
  52. void go(ll x, ll y){
  53. 	vis[x][y] = 1;
  54. 	T++;
  55. 	x1 = min(x1, x);
  56. 	x2 = max(x2, x);
  57. 	Y1 = min(Y1, y);
  58. 	y2 = max(y2, y);
  59. 	ll i;
  60. 	fo(i, 8){
  61. 		ll nx = x+dx[i];
  62. 		ll ny = y+dy[i];
  63. 		if(!val(nx, ny) or vis[nx][ny] or a[nx][ny] != 1) continue;
  64. 		go(nx, ny);
  65. 	}
  66. }
  67. ll sum(ll x1, ll Y1, ll x2, ll y2){
  68. 	return dp[x2][y2] + dp[x1-1][Y1-1] - dp[x1-1][y2] - dp[x2][Y1-1];
  69. }
  70. int main()
  71. {
  72. 	ios_base::sync_with_stdio(false);
  73. 	cin.tie(NULL);
  74. 	ll i,k,j;
  75. 	cin>>n>>m;
  76. 	fo(i, n) fo(j, m)cin>>a[i+1][j+1];
  77. 	fo(i, n+1) dp[i][0] = 0;
  78. 	fo(i, m+1) dp[0][i] = 0;
  79. 	Fo(i, 1, n+1)
  80. 	Fo(j, 1, m+1) dp[i][j] = a[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
  81. 	// cout<<sum(2,2,2,3)<<endl;
  82. 	Fo(i, 1, n+1)
  83. 		if(a[i][1] and !vis[i][1]) fill(i, 1);
  84. 	Fo(i, 1, n+1)
  85. 		if(a[i][m] and !vis[i][m]) fill(i, m);
  86.  
  87.  
  88. 	Fo(i, 1, m+1)
  89. 		if(a[1][i] and !vis[1][i]) fill(1, i);
  90.  
  91. 	Fo(i, 1, m+1)
  92. 		if(a[n][i] and !vis[n][i]) fill(n, i);
  93. 	ll ans = 0;
  94. 	Fo(i, 2, n)
  95. 	Fo(j, 2, m){
  96. 		if(vis[i][j] or a[i][j]==0) continue;
  97. 		x1 = Y1 = mod;
  98. 		x2 = y2 = 0;
  99. 		T = 0;
  100. 		go(i, j);
  101. 		// cout<<T<<" "<<x1<<" "<<Y1<<" "<<x2<<" "<<y2<<endl;
  102. 		if(sum(x1, Y1, x2, y2) == (x2-x1+1)*(y2-Y1+1)) ans = max(ans, T);
  103. 	}
  104. 	ans = ans==0?-1:ans;
  105. 	cout<<ans<<endl;
  106. 	return 0;
  107. }
Success #stdin #stdout 0s 27056KB
comments (?)
stdin
copy 
3 4
0 0 1 0
0 1 0 0
0 0 1 0
stdout
copy 
-1
https://ideone.com/MeF2yN
my template :)
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!