Source code for submission s1038

fm.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <queue>
  11. #include <utility>
  12.  
  13. using namespace std;
  14.  
  15.  
  16. vector<vector<char> > mapka;
  17. vector<int> intervalac;
  18.  
  19. int AR,AC,TR,TC, mocnina;
  20.  
  21. int spusti(int vrchol, pair<int,int> LH, pair<int,int> PD){
  22. if(PD.first-LH.first==1) {
  23. if(mapka[LH.first][LH.second]=='X') {
  24. intervalac[vrchol] = 1;
  25. return 1;
  26.  
  27. }
  28. else return 0;
  29. }
  30.  
  31. intervalac[vrchol] = spusti(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2))
  32. + spusti(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2))
  33. + spusti(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second))
  34. + spusti(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD);
  35.  
  36. return intervalac[vrchol];
  37. }
  38.  
  39. int pocet(int vrchol, pair<int,int> LH, pair<int,int> PD, pair<int,int> HlaLH, pair<int,int> HlaPD){
  40. if(HlaLH.first <= LH.first && HlaLH.second <= LH.second && HlaPD.first >= PD.first && HlaPD.second >= PD.second)
  41. return intervalac[vrchol];
  42. else if (HlaLH.first >= PD.first || HlaLH.second >= PD.second || HlaPD.first <= LH.first || HlaPD.second <= LH.second) return 0;
  43. else {
  44.  
  45. return pocet(vrchol * 4 + 1, LH, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), HlaLH, HlaPD)
  46. + pocet(vrchol * 4 + 2, make_pair((LH.first + PD.first) / 2, LH.second), make_pair (PD.first, (PD.second + LH.second) / 2), HlaLH, HlaPD)
  47. + pocet(vrchol * 4 + 3, make_pair(LH.first, (LH.second + PD.second) / 2), make_pair ((PD.first + LH.first) / 2, PD.second), HlaLH, HlaPD)
  48. + pocet(vrchol * 4 + 4, make_pair((LH.first + PD.first) / 2, (LH.second + PD.second) / 2), PD, HlaLH, HlaPD);
  49.  
  50. }
  51.  
  52. }
  53.  
  54. int skus(int x, int y){
  55. int vys = 0;
  56.  
  57. for(int i = x; i + TR < mocnina; i += TR){
  58. for(int j = y; j + TC < mocnina; j += TC){
  59.  
  60. //cout<<"od: ["<<i<<", "<<j<<"] po ["<<i+TR<<", "<<j+TC<<"] to je "<<pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC))<<endl;
  61.  
  62. if(pocet (0, make_pair(0,0), make_pair(mocnina,mocnina), make_pair(i,j), make_pair(i + TR, j + TC)) > 0) vys++;
  63. }
  64. }
  65.  
  66. return vys;
  67. }
  68.  
  69.  
  70. int main(){
  71. while(scanf("%d%d%d%d",&AR,&AC,&TR,&TC)!=EOF){
  72.  
  73. mapka.clear();
  74. intervalac.clear();
  75.  
  76. mocnina = 1;
  77. while(mocnina < TR+TR+AR+TR+TR) mocnina *= 2;
  78.  
  79. while(mocnina < TC+TC+AC+TC+TC) mocnina *= 2;
  80.  
  81. mapka.resize(mocnina, vector<char> (mocnina,'.'));
  82.  
  83. intervalac.resize(mocnina * mocnina * 2, 0);
  84.  
  85. for(int i = 0; i < AR; i++){
  86. string riadok;
  87. cin>>riadok;
  88. for(int j = 0; j < riadok.size(); j++){
  89. mapka[i + TR * 2][j + TC * 2] = riadok[j];
  90. }
  91. }
  92.  
  93. spusti(0,make_pair(0,0), make_pair(mocnina, mocnina));
  94.  
  95. /* for(int i = 0; i < mocnina; i++){
  96.   for(int j=0; j< mocnina; j++){
  97. cout<<mapka[i][j];
  98.  
  99.   }
  100.   cout<<endl;
  101.   }
  102.  
  103.   for(int i =0; i< mocnina * mocnina ; i++){
  104.   cout<<intervalac[i]<<" ";
  105.   }*/
  106.  
  107. int najmensie = 100000000;
  108.  
  109. for(int i = 0; i < TR; i++){
  110. for(int j = 0; j < TC; j++){
  111. najmensie = min(skus(i,j), najmensie);
  112. }
  113.  
  114. }
  115.  
  116. cout<<najmensie<<endl;
  117.  
  118. }
  119.  
  120. }