Source code for submission s810

fm.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. ///////////////////////////////////////////////////////////////////////////
  29.  
  30. const int MAX = 1300;
  31. int R, C, TR, TC;
  32. char in[MAX][MAX];
  33. int sum[MAX][MAX];
  34.  
  35. int get(int r1, int c1, int r2, int c2)
  36. {
  37. int res = sum[r2][c2];
  38. if (r1) res -= sum[r1-1][c2];
  39. if (c1) res -= sum[r2][c1-1];
  40. if (r1&&c1) res += sum[r1-1][c1-1];
  41. return res;
  42. }
  43.  
  44. int dp[200][200];
  45.  
  46. int main()
  47. {
  48. while (scanf("%d%d%d%d", &R, &C, &TR, &TC) == 4)
  49. {
  50. memset(sum, 0, sizeof(sum));
  51. REP(i, R)
  52. {
  53. scanf("%s", in[i]);
  54. REP(j, C) sum[i+TR][j+TC] = in[i][j] == 'X';
  55. }
  56. R += TR;
  57. C += TC;
  58.  
  59. REP(i, R+TR) REP(j, C+TC)
  60. {
  61. if (i) sum[i][j] += sum[i-1][j];
  62. if (j) sum[i][j] += sum[i][j-1];
  63. if (i&&j) sum[i][j] -= sum[i-1][j-1];
  64. }
  65.  
  66. memset(dp, 0, sizeof(dp));
  67. REP(i, R) REP(j, C)
  68. {
  69. if (get(i, j, i+TR-1, j+TC-1))
  70. dp[i%TR][j%TC] += 1;
  71. }
  72.  
  73. int res = INF;
  74. REP(i, TR) REP(j, TC)
  75. res = min(res, dp[i][j]);
  76. printf("%d\n", res);
  77. }
  78.  
  79. return 0;
  80. }