Source code for submission s749

fm.cpp

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4.  
  5. #include<cmath>
  6. #include<cctype>
  7. #include<climits>
  8. #include<algorithm>
  9. #include<utility>
  10. #include<string>
  11.  
  12. #include<deque>
  13. #include<list>
  14. #include<map>
  15. #include<queue>
  16. #include<set>
  17. #include<stack>
  18. #include<vector>
  19.  
  20.  
  21. using namespace std;
  22.  
  23. #define REP(i,N) for (int i = 0; i < (N); i++)
  24. #define FOR(i,a,b) for (int i = (a); i <= (b); i++)
  25. #define FORI(i,a,b) for (int i = (a); i < (b); i++)
  26. #define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--)
  27. #define DP(arg...) fprintf(stderr, ## arg)
  28.  
  29. typedef long long ll;
  30. typedef long double ld;
  31. typedef pair<int,int> ii;
  32.  
  33. int W, H;
  34. int w, h;
  35. int S[2222][2222];
  36. int res[1111][1111];
  37. char mapa[2222][2222];
  38.  
  39. int oblast(int x, int y) {
  40. 	int ans = S[x][y] + S[x-w][y-h];
  41. 	ans -= S[x][y-h] + S[x-w][y];
  42. 	return ans;
  43. }
  44.  
  45. void solve() {
  46. 	REP(i, W+4*w) REP(j, H+4*h) {
  47. 		S[i][j] = 0;
  48. 		mapa[i][j] = '.';
  49. 	}
  50. 	REP(i, w+5) REP(j, h+5) res[i][j] = 0;
  51. 	REP(i, W) REP(j, H) {
  52. 		char c; scanf(" %c", &c);
  53. 		mapa[i+w][j+h] = c;
  54. 	}
  55. 	FOR (i, 1, W+2*w) {
  56. 		int pref = 0;
  57. 		FOR (j, 1, H+2*h) {
  58. 			pref += (mapa[i][j]=='X')?1:0;
  59. 			S[i][j] = pref + S[i-1][j];
  60. 		}
  61. 	}
  62. 	FOR(i, w, W+2*w) FOR(j, h, H+2*h) {
  63. 		if (oblast(i, j)>0) res[i%w][j%h]++;
  64. 	}
  65. 	int ans = INT_MAX;
  66. 	REP(i, w) REP(j, h) ans = min(ans, res[i][j]);
  67. 	printf("%d\n", ans);
  68. }
  69.  
  70. int main() {
  71. 	while (scanf("%d%d%d%d", &W, &H, &w, &h) != EOF) {
  72. 		solve();
  73. 	}
  74. 	return 0;
  75. }
  76.