Source code for submission s959

five.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <iostream>
  7. #include <list>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <sstream>
  12. #include <stack>
  13. #include <string>
  14. #include <utility>
  15. #include <vector>
  16. using namespace std;
  17.  
  18. #define DEBUG(x) cerr << ">> " << #x << ": " << x << endl;
  19. #define REP(i,a) for (int i =0; i < (a);++i)
  20. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  21.  
  22. struct Point
  23. {
  24. int x;
  25. int y;
  26. Point(int a, int b)
  27. {
  28. x=a;y=b;
  29. }
  30. };
  31. int mapwidth, mapheight, tilewidth, tileheight;
  32. long long testcase = 0;
  33. char character;
  34. bool pixels[1000][1000];
  35. int tileFound[1000][1000];
  36. int firstX, firstY;
  37. int topleftx, toplefty;
  38. vector<Point> allpoints;
  39. int pointsCount;
  40.  
  41.  
  42. int gettileX(int x, int y)
  43. {
  44. // cerr << "Tile (" << x << "," << y << ") has X: " << (x-topleftx) / tilewidth << endl;
  45. return (x-topleftx) / tilewidth;
  46. }
  47. int gettileY(int x, int y)
  48. {
  49. // cerr << "Tile (" << x << "," << y << ") has Y: " << (y-toplefty) / tileheight << endl;
  50. return (y-toplefty) / tileheight;
  51. }
  52.  
  53. int main() {
  54. for (int x = 0; x < 1000;x ++)
  55. for (int y =0 ;y<1000;y++)
  56. {
  57. tileFound[x][y] = -1;
  58. }
  59. while (scanf("%d%d%d%d", &mapheight, &mapwidth, &tileheight, &tilewidth) != EOF)
  60. {
  61. scanf("%c", &character);
  62. long maxtc = 1000000;
  63. pointsCount = 0;
  64. // Load map
  65. for (int y =0 ;y <mapheight;y++)
  66. {
  67. for (int x = 0; x < mapwidth; x++)
  68. {
  69. scanf("%c", &character);
  70. pixels[x][y] = (character == 'X');
  71. if (pixels[x][y])
  72. {
  73. allpoints.push_back(Point(x,y));
  74. pointsCount++;
  75. }
  76. if (firstX == -1 && pixels[x][y])
  77. {
  78. firstX = x; firstY = y;
  79. }
  80. }
  81. scanf("%c", &character);
  82. }
  83.  
  84. for (int rfx = 0; rfx < tilewidth; rfx++)
  85. {
  86. for (int rfy = 0; rfy <tileheight;rfy++)
  87. {
  88. topleftx = -rfx;
  89. toplefty = -rfy;
  90. long tc = 0;
  91. for(vector<Point>::iterator it = allpoints.begin(); it != allpoints.end(); it++)
  92. {
  93. int tx = gettileX(it->x, it->y);
  94. int ty= gettileY(it->x, it->y);
  95. if (tileFound[tx][ty] < testcase)
  96. {
  97. tileFound[tx][ty] = testcase;
  98. //cout << "Testcase " << testcase << ": " << tx << "," << ty << endl;
  99. tc++;
  100. if (tc > maxtc) break;
  101. }
  102. }
  103. if (tc < maxtc)
  104. {
  105. maxtc = tc;
  106. }
  107. testcase++;
  108. }
  109. }
  110. printf("%ld\n", maxtc);
  111.  
  112. // Vector pop all
  113. for (int i = 0; i <pointsCount;i++)
  114. {
  115. allpoints.pop_back();
  116. }
  117. }
  118. return 0;
  119. }