fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long int
  6. #define mod 1000000007
  7. #define p push
  8. #define pb push_back
  9. #define mp make_pair
  10. #define f first
  11. #define s second
  12.  
  13. int n, m;
  14. int a[1007][1007], dp[1007][1007], DPRight[1007][1007], DPDown[1007][1007];
  15. int PrefixDown[1007][1007], PrefixRight[1007][1007];
  16. vector < pair < pair <int, int>, int> > ansv;
  17.  
  18.  
  19. int check(int x, int y, int h)
  20. {
  21. 	if(x + h > n || x - h < 1 || y + h > m || y - h < 1) return 0;
  22.  
  23. 	if(PrefixRight[x][y + h] - PrefixRight[x][y] != h) return 0;
  24. 	if(PrefixRight[x][y] - PrefixRight[x][y - h - 1] != h + 1) return 0;
  25. 	if(PrefixDown[x + h][y] - PrefixDown[x][y] != h) return 0;
  26. 	if(PrefixDown[x][y] - PrefixDown[x - h - 1][y] != h + 1) return 0;
  27.  
  28. 	return 1;
  29.  
  30. }
  31.  
  32. int fill(int x, int y, int h)
  33. {
  34.  
  35. 	ansv.pb(mp(mp(x, y), h));
  36.  
  37. 	DPRight[x + h + 1][y]--;
  38. 	DPRight[x - h][y]++;
  39. 	DPDown[x][y + h + 1]--;
  40. 	DPDown[x][y - h]++;
  41.  
  42. 	return 1;
  43.  
  44. }
  45.  
  46. int bsearch(int x, int y)
  47. {
  48. 	int low = 1, high = 1001, mid, ans = 0;
  49.  
  50. 	while(low <= high)
  51. 		{
  52. 			mid = (low + high) / 2;
  53.  
  54. 			if(check(x, y, mid)) {
  55. 				ans = mid;
  56. 				low = mid + 1;
  57. 			}
  58. 			else high = mid - 1;
  59. 		}
  60.  
  61. 	if(ans) fill(x, y, ans);
  62. 	return 0;
  63. }
  64.  
  65. signed main()
  66. 	{
  67. 		ios_base::sync_with_stdio(false);
  68. 		cin.tie(NULL);
  69.  
  70. 		int i, j, u, v;
  71. 		bool ans = 1;
  72. 		char x;
  73.  
  74. 		cin >> n >> m;
  75.  
  76. 		for(i = 1; i <= n; i++)
  77. 			{
  78. 				for(j = 1; j <= m; j++)
  79. 					{
  80. 						cin >> x;
  81. 						if(x == '*') a[i][j] = 1;
  82. 					}
  83. 			}
  84.  
  85. 		for(i = 1; i <= n; i++)
  86. 			for(j = 1; j <= m; j++)
  87. 				PrefixRight[i][j] = PrefixRight[i][j - 1] + a[i][j];
  88.  
  89. 		for(i = 1; i <= m; i++)
  90. 			for(j = 1; j <= n; j++)
  91. 				PrefixDown[j][i] = PrefixDown[j - 1][i] + a[j][i];
  92.  
  93.  
  94. 		for(i = 1; i <= n; i++)
  95. 			for(j = 1; j <= m; j++)
  96. 				if(a[i][j])
  97. 					bsearch(i, j);
  98.  
  99.  
  100. 		for(i = 1; i <= n; i++)
  101. 			for(j = 1; j <= m; j++)
  102. 				DPDown[i][j] = DPDown[i][j - 1] + DPDown[i][j];
  103.  
  104. 		for(i = 1; i <= m; i++)
  105. 			for(j = 1; j <= n; j++)
  106. 				DPRight[j][i] = DPRight[j - 1][i] + DPRight[j][i];
  107.  
  108.  
  109. 		for(i = 1; i <= n; i++)
  110. 			{
  111. 				for(j = 1; j <= m; j++) 
  112. 					if(a[i][j] && !(DPRight[i][j] || DPDown[i][j])) ans = 0;
  113. 			}
  114.  
  115. 		if(!ans) {
  116. 			cout << -1 << endl;
  117. 			return 0;
  118. 		}
  119.  
  120. 		cout << ansv.size() << endl;
  121. 		for(i = 0; i < ansv.size(); i++) cout << ansv[i].f.f << " " << ansv[i].f.s << " " << ansv[i].s << endl;
  122. 		return 0;
  123. 	}
Success #stdin #stdout 0s 4328KB
comments (?)
stdin 
5 5
.*...
****.
.****
..**.
.....
stdout 
3
2 2 1
3 3 1
3 4 1
https://ideone.com/cPp2so
language:
C++14 (clang 8.0)
created:
6 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!