fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int B,D; 
  8.     if(!(cin>>B>>D)) return 0;
  9.     vector<string> shape(D);
  10.     for(int j=0;j<D;j++) cin>>shape[j];
  11.     int W,H; cin>>W>>H;
  12.     vector<string> park(H);
  13.     for(int y=0;y<H;y++) cin>>park[y];
  14.  
  15.     vector<pair<int,int>> cells;
  16.     for(int j=0;j<D;j++) for(int i=0;i<B;i++) if(shape[j][i]=='O') cells.push_back({i,j});
  17.     if(cells.empty()){
  18.         for(int y=0;y<H;y++) cout<<park[y]<<"\n";
  19.         return 0;
  20.     }
  21.  
  22.     vector<pair<int,int>> cand;
  23.     cand.reserve((long long)W*H);
  24.     for(int y=0;y+ D<=H;y++) for(int x=0;x+ B<=W;x++) cand.push_back({x,y});
  25.  
  26.     auto feasiblePositions = [&](const vector<string>& g, int x, int y)->bool{
  27.         for(auto [dx,dy]:cells){
  28.             int gx=x+dx, gy=y+dy;
  29.             if(g[gy][gx]!='.') return false;
  30.             static int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
  31.             for(auto &d:dir){
  32.                 int nx=gx+d[0], ny=gy+d[1];
  33.                 if(0<=nx && nx<W && 0<=ny && ny<H){
  34.                     if(g[ny][nx]=='O') return false;
  35.                 }
  36.             }
  37.         }
  38.         return true;
  39.     };
  40.  
  41.     auto place = [&](vector<string>& g, int x, int y){
  42.         for(auto [dx,dy]:cells){
  43.             int gx=x+dx, gy=y+dy;
  44.             g[gy][gx]='O';
  45.         }
  46.     };
  47.  
  48.     vector<string> best=park, cur;
  49.     int bestCnt=-1;
  50.  
  51.     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  52.     vector<pair<int,int>> order=cand;
  53.  
  54.     int loops=500;
  55.     for(int iter=0;iter<loops;iter++){
  56.         cur=park;
  57.         shuffle(order.begin(), order.end(), rng);
  58.         int placed=0;
  59.         for(auto [x,y]:order){
  60.             if(feasiblePositions(cur,x,y)){
  61.                 place(cur,x,y);
  62.                 placed++;
  63.             }
  64.         }
  65.         if(placed>bestCnt){
  66.             bestCnt=placed;
  67.             best=cur;
  68.         }
  69.     }
  70.  
  71.     for(int y=0;y<H;y++) cout<<best[y]<<"\n";
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
4 3
O..O
OOOO
.O..
20 10
....................
.w......w.......ww..
....ww......w.w.....
.w.....w............
...w......w.........
w................ww.
....w...............
.w.....w........w.ww
............w.......
....w..............w
stdout 
..O..O......O..O....
.wOOOO.Ow.O.OOOOww..
...Oww.OOOO.wOw.O..O
.w.....wO..O..O.OOOO
.O.wO.O..OwOOOO..O..
wOOOO.OOOO..O...OwwO
..O.w..O..O..O..OOOO
Ow.O.O.wO.OOOO..wOww
OOOO.OOOO..Ow.......
.O..w.O............w
https://ideone.com/TzcLL1
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!