fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define st first
  6. #define nd second
  7. #define rd third
  8. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  9. #define RE(i, n) FOR(i, 1, n)
  10. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  11. #define REP(i, n) for(int i = 0;i <(n); ++i)
  12. #define VAR(v, i) __typeof(i) v=(i)
  13. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define SZ(x) ((int)(x).size())
  16. #define __builtin_ctz __builtin_ctzll
  17. #define __builtin_clz __builtin_clzll
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
  21. template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  22.   while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
  23. }
  24. #ifdef LOCAL
  25. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  26. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  27. #else
  28. #define debug(...) (__VA_ARGS__)
  29. #define debugv(x)
  30. #define cerr if(0)cout
  31. #endif
  32. #define next ____next
  33. #define prev ____prev
  34. #define left ____left
  35. #define hash ____hash
  36. typedef long long ll;
  37. typedef long double LD;
  38. typedef pair<int, int> PII;
  39. typedef pair<ll, ll> PLL;
  40. typedef vector<int> VI;
  41. typedef vector<VI> VVI;
  42. typedef vector<ll> VLL;
  43. typedef vector<pair<int, int> > VPII;
  44. typedef vector<pair<ll, ll> > VPLL;
  45.  
  46. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  47. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  48. template<class T1, class T2>
  49. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  50. template<class A, class B, class C> struct Triple { A first; B second; C third;
  51.   bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
  52. template<class T> void ResizeVec(T&, vector<int>) {}
  53. template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  54.   vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  55.   for (T& v : vec) { ResizeVec(v, sz); }
  56. }
  57. typedef Triple<int, int, int> TIII;
  58. template<class A, class B, class C>
  59. ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
  60. template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  61. template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  62. template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  63.  
  64. const int N = 505;
  65. int taken[N][N];
  66. int32_t main() {
  67.  
  68.   ios_base::sync_with_stdio(0);
  69.   cout << fixed << setprecision(10);
  70.   cerr << fixed << setprecision(10);
  71.   cin.tie(0);
  72.   //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  73.  
  74.   srand(clock());
  75.   int n, m;
  76.   cin>>n>>m;
  77.   vector<vector<char>> board(n + 2, vector<char>(m + 2));
  78.   RE (i, n) {
  79.     RE (j, m) {
  80.       cin>>board[i][j];
  81.     }
  82.   }
  83.   vector<VPII> dangos;
  84.   RE (i, n) {
  85.     RE (j, m) {
  86.       if (board[i][j] != 'W') { continue; }
  87.       FOR (ni, i - 1, i + 1) {
  88.         FOR (nj, j - 1, j + 1) {
  89.           if (ni == i && nj == j) { continue; }
  90.           if (board[ni][nj] == 'P' && board[2 * i - ni][2 * j - nj] == 'G') {
  91.             dangos.PB({{ni, nj}, {i, j}, {2 * i - ni, 2 * j - nj}});
  92.             if (dangos.back()[0] > dangos.back()[2]) {
  93.               swap(dangos.back()[0], dangos.back()[2]);
  94.             }
  95.           }
  96.         }
  97.       }
  98.     }
  99.   }
  100.   int best_res = 0;
  101.   vector<vector<char>> best_board;
  102.   REP (triess, 1) {
  103.     RE (i, n) {
  104.       RE (j, m) {
  105.         taken[i][j] = -1;
  106.       }
  107.     }
  108.     random_shuffle(ALL(dangos));
  109.     int res = 0;
  110.     //VI used(SZ(dangos));
  111.     auto Put = [&](int k) {
  112.       auto& dango = dangos[k];
  113.       REP (i, 3) {
  114.         assert(taken[dango[i].st][dango[i].nd] == -1);
  115.         taken[dango[i].st][dango[i].nd] = k;
  116.       }
  117.       res++;
  118.     };
  119.     auto Remove = [&](int k) {
  120.       auto& dango = dangos[k];
  121.       REP (i, 3) {
  122.         assert(taken[dango[i].st][dango[i].nd] == k);
  123.         taken[dango[i].st][dango[i].nd] = -1;
  124.       }
  125.       res--;
  126.     };
  127.     REP (ii, SZ(dangos)) {
  128.       auto dango = dangos[ii];
  129.       int can = 1;
  130.       for (auto p : dango) {
  131.         if (taken[p.st][p.nd] != -1) {
  132.           can = 0;
  133.         }
  134.       }
  135.       if (can) {
  136.         res++;
  137.         for (auto p : dango) {
  138.           taken[p.st][p.nd] = ii;
  139.         }
  140.       }
  141.     }
  142.     int last_improv = 0;
  143.     int tries = 0;
  144.     while (1) {
  145.       int i = rand() % SZ(dangos);
  146.       auto& dango = dangos[i];
  147.       if (taken[dango[0].st][dango[0].nd] == i) { continue; }
  148.       tries++;
  149.       int blocking = 0;
  150.       int last_blocking = -1;
  151.       for (auto p : dango) {
  152.         if (taken[p.st][p.nd] != -1) {
  153.           blocking++;
  154.           last_blocking = taken[p.st][p.nd];
  155.         }
  156.       }
  157.       if (blocking == 0) {
  158.         if (tries - last_improv > (int)1e6) {
  159.           debug(last_improv - tries, res);
  160.         }
  161.         last_improv = tries;
  162.       }
  163.       if (blocking <= 1) {
  164.         if (last_blocking != -1) {
  165.           Remove(last_blocking);
  166.         }
  167.         Put(i);
  168.       }
  169.       if (last_improv + 10000000 < tries) { // this constant value can be adjusted
  170.         break;
  171.       }
  172.     }
  173.  
  174.     vector<vector<char>> cand = board;
  175.     REP (i, SZ(dangos)) {
  176.       auto dango = dangos[i];
  177.       auto p = dango[1];
  178.       if (taken[p.st][p.nd] == i) {
  179.         if (dango[0] == PII{p.st - 1, p.nd - 1}) {
  180.           cand[p.st][p.nd] = '\\';
  181.         } else if (dango[0] == PII{p.st - 1, p.nd}) {
  182.           cand[p.st][p.nd] = '|';
  183.         } else if (dango[0] == PII{p.st - 1, p.nd + 1}) {
  184.           cand[p.st][p.nd] = '/';
  185.         } else {
  186.           cand[p.st][p.nd] = '-';
  187.         }
  188.       }
  189.     }
  190.     if (res > best_res) {
  191.       best_board = cand;
  192.     }
  193.     maxi(best_res, res);
  194.   }
  195.   debug(best_res);
  196.   RE (i, n) {
  197.     RE (j, m) {
  198.       cout<<best_board[i][j];
  199.     }
  200.     cout<<endl;
  201.   }
  202.   //cout<<best_res<<endl;
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.   return 0;
  231. }
  232.  
Success #stdin #stdout 0.99s 4448KB
comments (?)
stdin
copy 
3 4
PWGP
WGPW
GWPG
stdout
copy 
P-GP
WGP|
G-PG
https://ideone.com/K3nyE4
language:
C++14 (gcc 8.3)
created:
4 years 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!