Advertisement
Guest User

Untitled

a guest
Mar 1st, 2015
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.44 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. #define ROTATIONS 1
  8. // 1-40 max
  9.  
  10. #define MAX_CNT 50
  11. // max count of houses
  12.  
  13. //Comment:
  14. // FILL should be true for good effects
  15. // if your computer still calculates it in sensible time, increase
  16. // ROTATIONS. But it increases computational time by ROT^2
  17.  
  18. struct pt{
  19. int x,y;
  20. };
  21.  
  22. pt operator+(pt a,pt b){
  23. return {a.x+b.x,a.y+b.y};
  24. }
  25.  
  26. vector<vector<pt>> all_sh;
  27.  
  28. struct building{
  29. int ind;
  30. pt pos;
  31. };
  32.  
  33. bool try_put(pt point, const vector<string>& mp){
  34. if(point.y<0 || point.y>=mp[0].length())return false;
  35. if(point.x<0 || point.x>=mp.size())return false;
  36. if(mp[point.x][point.y]=='#'){return false;}
  37. return true;
  38. }
  39.  
  40. bool try_put(building bd, const vector<string>& mp,
  41. vector<string>& newmp, int& trees){
  42. int ind=bd.ind;
  43. pt pos=bd.pos;
  44.  
  45. for(int i=0;i<6;i++){
  46. if(!try_put(all_sh[ind][i]+pos,mp))return false;
  47. }
  48.  
  49. newmp=mp;
  50. trees=0;
  51. for(int i=0;i<6;i++){
  52. pt p=all_sh[ind][i]+pos;
  53. if(mp[p.x][p.y]=='X'){trees++;}
  54. newmp[p.x][p.y]='#';
  55. }
  56. return true;
  57. }
  58.  
  59. int abs(int a){
  60. if(a<0){return -a;}
  61. return a;
  62. }
  63.  
  64. int touch(pt a,pt b){
  65. if(a.x==b.x && a.y==b.y){return 1;}
  66. if(a.x==b.x){
  67. if(abs(a.y-b.y)==1){return 2;}
  68. }
  69. if(a.y==b.y){
  70. if(abs(a.x-b.x)==1){return 2;}
  71. }
  72. return 0;
  73. }
  74.  
  75. int touch(building bd1,building bd2){
  76. //returns 0 if buildings cross
  77. //otherwise, # of common walls
  78. int ind1=bd1.ind;
  79. pt p1=bd1.pos;
  80. int ind2=bd2.ind;
  81. pt p2=bd2.pos;
  82.  
  83. int cnt=0;
  84. for(int i=0;i<6;i++){
  85. for(int j=0;j<6;j++){
  86. int s=touch(p1+all_sh[ind1][i],p2+all_sh[ind2][j]);
  87. if(s==1){//cross
  88. return false;
  89. }
  90. if(s==2){//touch
  91. cnt++;
  92. }
  93. }
  94. }
  95. return cnt;
  96. }
  97.  
  98. void solve(vector<string> mp){
  99. int n=mp.size();
  100. //printf("N= %d\n",n);
  101. int m=mp[0].length();
  102. //printf("M= %d\n",m);
  103. vector<building>gardens;
  104. vector<building>houses;
  105.  
  106. bool anything;
  107. int total_score=0;
  108. do{
  109. anything=false;
  110. int g_best=-2000;
  111. building gbestg,gbesth;
  112. vector<string>gmp;
  113. for(int i=0;i<n;i++){
  114. for(int j=0;j<m;j++){
  115. for(int k=0;k<ROTATIONS;k++){
  116. vector<string>newmp;
  117. int trees;
  118. building garden={k,{i,j}};
  119. if(try_put(garden,mp,newmp,trees)){
  120. //printf("Can put garden at %d,%d with %d trees\n",i,j,trees);
  121. //for(int a=0;a<newmp.size();a++){
  122. // printf("%s\n",newmp[a].c_str());
  123. //}
  124. int score1=3+2*trees;
  125.  
  126. int bestscore2=-20000;
  127. building besth;
  128. vector<string>bestmp;
  129. for(int i2=i-12;i2<i+12;i2++){
  130. for(int j2=j-12;j2<j+12;j2++){
  131. for(int k2=0;k2<ROTATIONS;k2++){
  132. building house={k2,{i2,j2}};
  133. vector<string>newmp2;
  134. if(try_put(house,newmp,newmp2,trees)){
  135. if(touch(garden,house)){
  136. int score2=-2*trees;
  137. if(score2>bestscore2){
  138. bestscore2=score2;
  139. besth=house;
  140. bestmp=newmp2;
  141. }
  142. }
  143. }
  144. }
  145. }
  146. }
  147. score1+=bestscore2;
  148. if(score1>g_best){
  149. g_best=score1;
  150. gbestg=garden;
  151. gbesth=besth;
  152. gmp=bestmp;
  153. }
  154.  
  155. }
  156. }
  157. }
  158. }
  159. //printf("With one more builden: %d\n",g_best);
  160. //for(int a=0;a<gmp.size();a++){
  161. // printf("%s\n",gmp[a].c_str());
  162. //}
  163. if(g_best>1 || gardens.size()==0){//adding buildings!
  164. gardens.push_back(gbestg);
  165. houses.push_back(gbesth);
  166. mp=gmp;
  167. total_score+=g_best;
  168. anything=gardens.size()<MAX_CNT;
  169. }
  170. } while(anything);
  171. for(int i=0;i<houses.size();i++){
  172. for(int j=0;j<houses.size();j++){
  173. if(i==j){continue;}
  174. total_score-=touch(houses[i],houses[j]);
  175. }
  176. }
  177. printf("%d %d\n",houses.size(),total_score);
  178. for(int i=0;i<houses.size();i++){
  179. printf("%c %d %d %d ",'a'+houses[i].ind%10,houses[i].ind/10,houses[i].pos.y+1,
  180. houses[i].pos.x+1);
  181. printf("%c %d %d %d\n",'a'+gardens[i].ind%10,gardens[i].ind/10,
  182. gardens[i].pos.y+1,
  183. gardens[i].pos.x+1);
  184. }
  185. }
  186.  
  187. vector<pt> basicshapes[10]={
  188. { {0,0}, {0,1}, {0,2}, {0,3}, {1,1}, {1,2} },
  189. { {0,0}, {0,1}, {0,2}, {1,0}, {1,1}, {2,0} },
  190. { {0,0}, {0,1}, {0,2}, {1,3}, {-1,1},{-1,2}},
  191. { {0,0}, {0,1}, {0,2}, {0,3}, {-1,2},{-1,3}},
  192. { {0,0}, {0,1}, {0,2}, {0,3}, {1,3}, {2,3} },
  193. { {0,0}, {0,1}, {0,2}, {0,3}, {0,4}, {0,5} },
  194. { {0,0}, {0,1}, {1,0}, {2,0}, {3,0}, {3,1} },
  195. { {0,0}, {0,1}, {0,2}, {1,0}, {1,2}, {2,2} },
  196. { {0,0}, {1,0}, {1,1}, {1,2}, {1,3}, {2,3} },
  197. { {0,0}, {0,1}, {0,2}, {1,1}, {2,0}, {2,1} }
  198. };
  199.  
  200. vector<pt> rotateshape(vector<pt>sh){
  201. vector<pt> ret;
  202. for(int i=0;i<sh.size();i++){
  203. ret.push_back({sh[i].y,-sh[i].x});
  204. }
  205. return ret;
  206. }
  207.  
  208. void testshape(vector<pt>sh){
  209. const int MAX = 16;
  210. char buff[MAX][MAX];
  211. for(int x=0;x<MAX;x++){
  212. for(int y=0;y<MAX;y++){
  213. buff[x][y]='.';
  214. }
  215. }
  216. for(int j=0;j<6;j++){
  217. buff[sh[j].y+MAX/2][sh[j].x+MAX/2]='x';
  218. }
  219. for(int j=0;j<MAX;j++){
  220. buff[j][MAX-1]=0;
  221. printf("%s\n",buff[j]);
  222. }
  223. }
  224.  
  225.  
  226. int main(){
  227. for(int i=0;i<10;i++){
  228. all_sh.push_back(basicshapes[i]);
  229. }
  230. for(int i=0;i<30;i++){
  231. all_sh.push_back(rotateshape(all_sh[i]));
  232. }
  233. for(int i=0;i<40;i++){
  234. for(int j=0;j<6;j++){
  235. int tmp=all_sh[i][j].x;
  236. all_sh[i][j].x=all_sh[i][j].y;
  237. all_sh[i][j].y=tmp;
  238. }
  239. }
  240.  
  241. int t;
  242. scanf("%d",&t);
  243. while(t--){
  244. int n,m;
  245. scanf("%d %d",&n,&m);
  246. vector<string>mp;
  247. char buff[209];
  248. for(int i=0;i<n;i++){
  249. scanf("%s",buff);
  250. string str(buff);
  251. mp.push_back(str);
  252. }
  253. solve(mp);
  254. }
  255.  
  256. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement