Source code for submission s788

fm.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <string>
  7. #include <deque>
  8. #include <list>
  9. #include <map>
  10. #include <queue>
  11. #include <set>
  12. #include <stack>
  13. #include <vector>
  14. using namespace std;
  15.  
  16. //#define debug printf
  17. #define debug blackhole
  18. void blackhole(...) {}
  19.  
  20. int Ar,Ac,Tr,Tc;
  21. bool TAKEN[2000][2000]; // [Ar][Ac]
  22.  
  23. int P[2000][2000]; // !!! od -Tr, -Tc do Ar, Ac
  24. int Q[2000][2000];
  25.  
  26. inline int is_taken(int x, int y) {
  27. if (x < 0 || y < 0 || x >= Ar || y >= Ac) return 0;
  28. return TAKEN[x][y] ? 1 : 0;
  29. }
  30.  
  31. void build() {
  32. for (int i=0;i<2000;i++) {
  33. for (int j=0;j<2000;j++) {
  34. P[i][j] = 0; Q[i][j] = 0;
  35. }
  36. }
  37. for (int r = -Tr; r < Ar + Tr; r++){
  38. for (int c = -Tc; c < Ac + Tc; c++) {
  39. P[r+Tr][c+Tc+1] += P[r+Tr][c+Tc] + is_taken(r, c + Tc) - is_taken(r, c);
  40. }
  41. }
  42. for (int c = -Tc; c < Ac + Ac; c++) {
  43. for (int r = -Tr; r < Ar + Ar; r++) {
  44. Q[r+Tr+1][c+Tc] += Q[r+Tr][c+Tc] + P[r+Tr+Tr][c+Tc] - P[r+Tr][c+Tc];
  45. }
  46. }
  47. }
  48.  
  49. bool free_tile(int sx, int sy) {
  50. return Q[sx+Tr][sy+Tc] == 0;
  51. }
  52.  
  53. long tiles_needed_for(int dx, int dy) {
  54. long taken = 0;
  55. debug("dx=%d dy=%d => ", dx,dy);
  56. for (int qx = -dx; qx < Ar; qx+=Tr) {
  57. for (int qy = -dy; qy < Ac; qy+=Tc) {
  58. if (!free_tile(qx,qy)) {
  59. taken += 1;
  60. debug("(%d,%d) ", qx,qy);
  61. }
  62. }
  63. }
  64. debug(" ---> %ld\n", taken);
  65. return taken;
  66. }
  67.  
  68. void debug_R_Q() {
  69. debug("vstup: \n");
  70. for (int r=-Tr; r<Ar+Tr; r++) {
  71. for (int c = -Tc; c<Ac+Tc; c++) {
  72. debug(" %c ", is_taken(r,c) ? 'X' : '.');
  73. }
  74. debug("\n");
  75. }
  76. debug("\n");
  77.  
  78. debug("P: \n");
  79. for (int r=-Tr; r<Ar+Tr; r++) {
  80. for (int c = -Tc; c<Ac+Tc; c++) {
  81. debug("%02d ", P[r][c]);
  82. }
  83. debug("\n");
  84. }
  85. debug("\n");
  86.  
  87. debug("Q: \n");
  88. for (int r=-Tr; r<Ar+Tr; r++) {
  89. for (int c = -Tc; c<Ac+Tc; c++) {
  90. debug("%02d ", Q[r][c]);
  91. }
  92. debug("\n");
  93. }
  94. debug("\n");
  95. }
  96.  
  97. void solve() {
  98. build();
  99. debug_R_Q();
  100. long best = -1;
  101. for (int dx = 0; dx < Tr; dx++) {
  102. for (int dy = 0; dy < Tr; dy++) {
  103. long tiles = tiles_needed_for(dx, dy);
  104. if (best == -1 || best > tiles) {
  105. best = tiles;
  106. }
  107. }
  108. }
  109. printf("%ld\n", best);
  110. }
  111.  
  112. int main() {
  113. while (true) {
  114. if (scanf("%d%d%d%d",&Ar,&Ac,&Tr,&Tc) != 4) break;
  115. for (int i = 0; i < Ar; i++) {
  116. char line[10000];
  117. scanf("%s", line);
  118. for (int j=0;j<Ac;j++) {
  119. TAKEN[i][j] = line[j] == 'X';
  120. }
  121. }
  122. solve();
  123. }
  124. return 0;
  125. }
  126.