Source code for submission s685

fm.cpp

  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <sstream>
  7. #include <map>
  8. #include <set>
  9. #include <queue>
  10. #include <vector>
  11.  
  12. using namespace std;
  13.  
  14. #define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
  15. #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
  16. #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
  17.  
  18. #define PB push_back
  19. #define MP make_pair
  20.  
  21. #define MM(co, cim) memset((co), (cim), sizeof((co)))
  22.  
  23. #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
  24.  
  25. int w, h, tw, th;
  26. char map1[1207][1207];
  27. char map2[1207][1207];
  28. char map3[1207][1207];
  29.  
  30. int main ()
  31. {
  32.  
  33. 	while(scanf("%d%d%d%d", &h, &w, &th, &tw) == 4) {
  34. 		FOR(i,0,1207) FOR(j,0,1207) map1[i][j] = map2[i][j] = map3[i][j] = '.';
  35. 		int full;
  36.  
  37. 		FOR(r,0,h) {
  38. 			scanf("%s", &(map1[r+th][tw]));
  39. 			map1[r+th][w+tw] = '.';
  40. 		}
  41.  
  42. 		w += 2*tw;
  43. 		h += 2*th;
  44.  
  45. 		FOR(r,0,h) {
  46. 			full = 0;
  47. 			FORDE(c,w-1,0) {
  48. 				if(map1[r][c] == 'X') full++;
  49. 				if(c+tw < w && map1[r][c+tw] == 'X') full--;
  50. 				if(full == 0) map2[r][c] = '.';
  51. 				else map2[r][c] = 'X';
  52. 			}
  53. 		}
  54.  
  55. 		FOR(c,0,w) {
  56. 			full = 0;
  57. 			FORDE(r,h-1,0) {
  58. 				if(map2[r][c] == 'X') full++;
  59. 				if(r+th < h && map2[r+th][c] == 'X') full--;
  60. 				if(full == 0) map3[r][c] = '.';
  61. 				else map3[r][c] = 'X';
  62. 			}
  63. 		}		
  64.  
  65. 		int mi = 1000000000;		
  66. 		FOR(dr,0,th) {
  67. 			FOR(dc,0,tw) {
  68. 				int sum = 0;
  69. 				for(int r = dr; r < h; r += th) {
  70. 					for(int c = dc; c < w; c += tw) {
  71. 						if(map3[r][c] == 'X') sum++;
  72. 					}
  73. 				}
  74. 				mi = min(mi,sum);
  75. 			}
  76. 		}
  77.  
  78. 		printf("%d\n", mi);
  79.  
  80. 		/*
  81. 		FOR(r,0,h) {
  82. 			FOR(c,0,w) {
  83. 				printf("%c", map1[r][c]);
  84. 			}
  85. 			printf("\n");
  86. 		}
  87. 		printf("\n");
  88. 				FOR(r,0,h) {
  89. 			FOR(c,0,w) {
  90. 				printf("%c", map2[r][c]);
  91. 			}
  92. 			printf("\n");
  93. 		}
  94. 		printf("\n");
  95. 				FOR(r,0,h) {
  96. 			FOR(c,0,w) {
  97. 				printf("%c", map3[r][c]);
  98. 			}
  99. 			printf("\n");
  100. 		}
  101. 		printf("\n");
  102. 		*/
  103. 	}
  104.   return 0;
  105. }
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.