Source code for submission s1128

fm.cpp

  1. #include <iostream>
  2. #include <set>
  3. #include <stdio.h>
  4. #include <utility>
  5. #include <map>
  6. #include <string>
  7. #include <sstream>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <climits>
  11. using namespace std;
  12.  
  13. int main(){
  14. int H, W;
  15. while(cin >> H >> W){
  16. int h, w;
  17. cin >> h >> w;
  18. vector<vector<int> > pref(H+2*h+20, vector<int>(W+2*w+20));
  19. vector<vector<bool> > image(H, vector<bool>(W));
  20. for(int i=0; i<H; ++i){
  21. string s;
  22. cin >> s;
  23. for(int j=0; j<W; ++j){
  24. if(s[j] == '.') image[i][j] = false;
  25. else image[i][j] = true;
  26. }
  27. }
  28. for(int i=0; i<H; ++i){
  29. for(int j=0; j<W; ++j){
  30. pref[i+h+1][j+w+1] = pref[i+h-1+1][j+w+1] + pref[i+h+1][j+w-1+1] - pref[i+h-1+1][j+w-1+1];
  31. if(image[i][j]) pref[i+h+1][j+w+1]++;
  32. }
  33. }
  34. for(int i=H+h; i<H+2*h; ++i){
  35. for(int j=0; j<W+2*w; ++j){
  36. pref[i+1][j+1] = pref[i-1+1][j+1];
  37. }
  38. }
  39. for(int j=W+w; j<W+2*w; ++j){
  40. for(int i=0; i<H+2*h; ++i){
  41. pref[i+1][j+1] = pref[i+1][j-1+1];
  42. }
  43. }
  44. int minimum = INT_MAX;
  45. for(int i=0; i<h; ++i){
  46. for(int j=0; j<w; ++j){
  47. int num = 0;
  48. for(int k=0; k<H/h+2; ++k){
  49. for(int l=0; l<W/w+2; ++l){
  50. //if(com_pref(i+k*h, j+l*w) > 0) num++;
  51. int p1 = i+k*h, p2 = j+l*w;
  52. int x = 0;
  53. if(p1 == 0 && p2 == 0){
  54. x = pref[p1+h-1+1][p2+w-1+1];
  55. }
  56. else if(p1 == 0){
  57. x = pref[p1+h-1+1][p2+w-1+1] - pref[p1+h-1+1][p2-1+1];
  58. }
  59. else if(p2 == 0){
  60. x = pref[p1+h-1+1][p2+w-1+1] - pref[p1-1+1][p2+w-1+1];
  61. }
  62. else{
  63. x = pref[p1+h-1+1][p2+w-1+1] - pref[p1-1+1][p2+w-1+1] - pref[p1+h-1+1][p2-1+1] + pref[p1-1+1][p2-1+1];
  64. }
  65. if(x>0) num++;
  66. }
  67. }
  68. minimum = min(num, minimum);
  69. }
  70. }
  71. cout << minimum << '\n';
  72.  
  73. }
  74.  
  75. }
  76.