提出 #62335709

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long;
using Graph = vector<vector<ll>>;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define MOD 1000000007
#define INF 2147483647
#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vcsort(x) sort(all(x))
#define vcstsort(x) stable_sort(all(x))
#define rev(x) reverse(all(x))
#define vcsum(x) accumulate(all(x), 0)//llなら0を0LLに
#define vcmax(x) *max_element(all(x))
#define vcmin(x) *min_element(all(x))
int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1, 1};
template <typename T> bool chmin(T &a, T b) {
  if (a > b)
    a = b;
  return true;
}
struct corr {
  int r;
  int c;
  int d;
  bool operator<(const corr &a) { return d < a.d; }
};
ll ncr(ll n, ll r, ll mod = MOD) {
  ll numerator = 1, denominator = 1;
  rng(i, 0, r) numerator = (numerator * (n - i)) % mod;
  rng(i, 0, r) denominator = (denominator * (r - i)) % mod;
  return numerator / denominator;
}
bool xyok(int r, int c, int h, int w) {
  return (r >= 0 && r < h && c >= 0 && c < w);
}
void fix(int a) { cout << fixed << setprecision(a); }
void outYN(bool a) { cout << (a ? "Yes" : "No") << endl; }
/*---------------------------------------------------------------------------------------------------------*/

class GameBoard{
  public:
  int n,t = 0;
  vector<string> grid;
  vector<pair<int,int>> ans;
  GameBoard(int n, vector<string> grid):n(n),grid(grid){}
 
  int count_onis(){
    int cnt = 0;
    rep(i, n) rep(j, n) if(grid[i][j]=='x') cnt++;
    return cnt;
  }

  pair<int,int> oni_pos(){
    vector<pair<int,int>> oni(0);
    rep(i,n){
      rep(j,n){
        if(grid[i][j] == 'x') oni.pb({i,j});
      }
    }
    if(oni.size() == 0) return make_pair(-1,-1);

    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, oni.size() - 1);
    return oni[dis(gen)];
  }
  void move(int a,int p){
    t++;
    if(a == 0){
      rep(i,n-1) grid[p][i] = grid[p][i+1]; 
      grid[p][n-1] = '.';
      ans.pb({0,p});
      // cout << "L " << p << endl;
    }else if(a == 1){
      rep(i,n-1) grid[p][n-1-i] = grid[p][n-2-i]; 
      grid[p][0] = '.';
      ans.pb({1,p});
      // cout << "R " << p << endl;
    }else if(a == 2){
      rep(i,n-1) grid[i][p] = grid[i+1][p]; 
      grid[n-1][p] = '.';
      ans.pb({2,p});
      // cout << "U " << p << endl;
    }else if(a == 3){
      rep(i,n-1) grid[n-1-i][p] = grid[n-2-i][p]; 
      grid[0][p] = '.';
      ans.pb({3,p});
      // cout << "D " << p << endl;
    }
  }
  void answer(){for(auto [a,p]:ans)cout << "LRUD"[a] << " " << p << endl;}

  ll score(){
    int oni = 0,hukukill = 0;
    rep(i,n){
      rep(j,n){
        if(grid[i][j] == 'x') oni++;
        if(grid[i][j] == 'o') hukukill++;
      }
    }
    hukukill = 2*n-hukukill;
    if(oni > 0 || hukukill>0) return (4*n*n)-n*(oni+hukukill);
    else return 8*n*n-t;
  }

  void board_show(){
    rep(i,n){
      rep(j,n){
        clog << grid[i][j];
      }
      clog << endl;
    }
  }

  void solve() {
    while (oni_pos() != make_pair(-1, -1)) {
      // clog << "score: " << score() << endl;
      auto [i, j] = oni_pos();
      // clog << i << " " << j << endl;
      // L R U D
      vector<pair<int, int>> diff_ang;
      rep(a, 4) {
        bool flag = true;
        int ni = i + my[a], nj = j + mx[a];
        while (xyok(ni, nj, n, n)) {
          if (grid[ni][nj] == 'o') {
            flag = false;
            break;
          }
          ni += my[a];
          nj += mx[a];
        }
        if (flag)
          diff_ang.pb({abs(ni - i) + abs(nj - j), a});
      }
      if (diff_ang.size() == 0)
        continue;

      sort(all(diff_ang), [](pair<int, int> a, pair<int, int> b) {
        return a.first < b.first;
      });

      auto [d, ang] = diff_ang[0];
      // fprintf(stderr, "[%d %d] %c\n",i,j,"LRUD"[ang]);

      int search = 0;
      if(ang == 0) search = 1;
      else if(ang == 1) search = 0;
      else if(ang == 2) search = 3;
      else if(ang == 3) search = 2;
      int ni = i + my[search], nj = j + mx[search];
      while (xyok(ni, nj, n, n)&&grid[ni][nj] != 'o') {
          if (grid[ni][nj] == 'x'){
            i = ni;
            j = nj;
          }
          ni += my[search];
          nj += mx[search];
      }


      if (count_onis()> 1) {
        bool empty = true;
        switch (ang) {
        case 0:
          rep(o, j + 1) move(0, i);
          rep(o, n) if (grid[i][o] != '.') empty = false;
          if(!empty)rep(o, j + 1) move(1, i);
          break;
        case 1:
          rep(o, n - j) move(1, i);
          rep(o, n) if (grid[i][o] != '.') empty = false;
          if(!empty)rep(o, n - j) move(0, i);
          break;
        case 2:
          rep(o, i + 1) move(2, j);
          rep(o, n) if (grid[o][j] != '.') empty = false;
          if(!empty)rep(o, i + 1) move(3, j);
          break;
        case 3:
          rep(o, n - i) move(3, j);
          rep(o, n) if (grid[o][j] != '.') empty = false;
          if(!empty)rep(o, n - i) move(2, j);
          break;

        case -1:
          clog << "error" << endl;
          exit(1);
          break;
        }
      } else {
        switch (ang) {
        case 0:
          rep(o, j + 1) move(0, i);
          break;
        case 1:
          rep(o, n - j) move(1, i);
          break;
        case 2:
          rep(o, i + 1) move(2, j);
          break;
        case 3:
          rep(o, n - i) move(3, j);
          break;

        case -1:
          clog << "error" << endl;
          exit(1);
          break;
        }
      }
    }
  }
};

int main() { 
  auto start = chrono::steady_clock::now();
  int n = 20;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  GameBoard gb(n,s);
  int max_score = 0;
  auto best=gb;
  while(chrono::duration<double>(chrono::steady_clock::now()-start).count() < 1.9) {
    auto cur = gb;
    cur.solve();
    int cur_score = cur.score();
    if(cur_score > max_score){
      max_score = cur_score;
      best = cur;
    }
  }
  best.answer();
  return 0;
}

提出情報

ジャッジ結果