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