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
stdin
5 5
.*...
****.
.****
..**.
.....
stdout
3
2 2 1
3 3 1
3 4 1