Submission #1173305

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int vy[] = {-1, 0, 1, 0, 0}, vx[] = {0, 1, 0, -1, 0};
const string vv = "URDL-";


int H, W, K, T, A[450], B[450], C[450], D[450];

bool isover(int y, int x)
{
  return (y < 0 || y >= H || x < 0 || x >= W);
}

int getCost(int y, int x, int id)
{
  return (abs(y - C[id]) + abs(x - D[id]));
}


struct State
{
  int mas[30][30];
  vector< string > dd;
  int score;

  State()
  {
    memset(mas, -1, sizeof(mas));
  }

  int getScore()
  {
    int Pd = 20;
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        if(~mas[i][j]) Pd += abs(C[mas[i][j]] - i) + abs(D[mas[i][j]] - j);
      }
    }
    double Pt = 10 + (int) dd.back().size() * 0.01;
    return ((int) ceil(10000000 / (Pd * Pt)));
  }


};

int main()
{
  cin >> H >> W >> K >> T;

  int S[500][500];
  memset(S, -1, sizeof(S));

  for(int i = 0; i < K; i++) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    --A[i], --B[i], --C[i], --D[i];
    S[A[i]][B[i]] = i;
  }

  int lim = 650;
  char dd[lim][450];

  vector< pair< int, int > > vs;
  for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) vs.emplace_back(i, j);
  
  for(int i = 0; i < lim; i++) {
    int T[500][500];
    memset(T, -1, sizeof(T));

    sort(begin(vs), end(vs));
    random_shuffle(begin(vs), end(vs));
    for(auto& pp : vs) {
      int j = pp.first;
      int k = pp.second;
      if(~S[j][k]) {
        char flop = '-';
        int id = S[j][k];

          int smallest = 114514;
          for(int l = 0; l < 4; l++) {
            int ny = j + vy[l], nx = k + vx[l];
            if(isover(ny, nx)) continue;
            int curdist = getCost(ny, nx, id);
            if(curdist - getCost(j, k, id) == 2) continue;
            if(T[ny][nx] == -1 && S[ny][nx] == -1) smallest = min(smallest, curdist);
          }
          vector< int > ch;
          for(int l = 0; l < 4; l++) {
            int ny = j + vy[l], nx = k + vx[l];
            if(isover(ny, nx)) continue;
            int curdist = getCost(ny, nx, id);
            if(T[ny][nx] == -1 && S[ny][nx] == -1 && smallest == curdist) ch.push_back(l);
          }
          if(!ch.empty()) flop = vv[ch[rand() % ch.size()]];

        int dir = vv.find(flop);
        T[j + vy[dir]][k + vx[dir]] = id;
        dd[i][id] = flop;
      }
      
    }
    swap(S, T);
  }

  cout << lim << endl;
  for(int i = 0; i < lim; i++) {
    for(int j = 0; j < K; j++) cout << dd[i][j];
    cout << endl;
  }
}

Submission Info

Judge Result