Submission #1173548

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int dx[] = {0, +1, 0, -1, 0};
const int dy[] = {-1, 0, +1, 0, 0};
const string DIRS = "URDL-";
const int MAX_HW = 30;
class XorShift {
  static const int MAX = numeric_limits<int>::max();
  int x = 123456789, y = 362436069, z = 521288629, w = 88675123;

public:
  XorShift() {}
  XorShift(int seed) {
    x ^= seed;
    y ^= x << 10 & seed;
    w ^= y >> 20 | seed;
    z ^= w & x;
  }
  int next() {
    int t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  }
  int next(int min_value, int max_value) {
    int range = max_value - min_value;
    return (sample() * range) + min_value;
  }
  double sample() { return next() * 1.0 / MAX; }
} rnd;

struct Car{
  int idx;
  pii src;
  pii goal;
  Car(){}
  Car(int idx, pii src, pii goal):idx(idx),src(src),goal(goal){}
  bool operator < (const Car &right) const {
    int cost1 = abs(src.first - goal.first) + (src.second - goal.second);
    int cost2 = abs(right.src.first - right.goal.first) + (right.src.second - right.goal.second);
    if (cost1 != cost2){
      return cost1 < cost2;
    }
    return idx < right.idx;
  }
};
bool is_out(int y, int x){
  if (y < 0 or y >= MAX_HW or x < 0 or x >= MAX_HW){
    return true;
  }
  return false;
}
vector<Car> input(){
  vector<Car> cars;
  int H,W,K,T;
  cin >> H >> W >> K >> T;

  for (int i = 0; i < K; i++){
    int A,B,C,D;
    cin >> A >> B >> C >> D;
    A--,B--,C--,D--;
    cars.emplace_back(Car(i, mp(A,B), mp(C, D)));
  }
  return cars;
}

struct State{
  vector<Car> cars;
  double score;
  shared_ptr<State> parent;
  bitset<900> visited;//30 x 30
  State(){
    this->parent = NULL;
  }
  State(const State& state):cars(state.cars),score(state.score),visited(state.visited){
    this->parent = NULL;
  }
  bool operator < (const State &right) const {
    return score < right.score;
  }
};


double calc_score(const vector<Car> &cars, int L){
  double score = 1e7;
  int PD = 20;
  int PL = 10 + 0.01 * L;
  for (const Car &car : cars){
    int diff_y = abs(car.src.first - car.goal.first);
    int diff_x = abs(car.src.second - car.goal.second);
    PD += diff_x + diff_y;
  }
  return score / (PD * PL);
}
void simulate_next_state(const State &state, priority_queue<State> &beams, int L){
  State next_state(state);
  next_state.parent = make_shared<State>(state);
  vector<Car>& cars = next_state.cars;
  for (Car &car : cars){
    int next_dir = rnd.next() % 5;
    int y = car.src.first;
    int x = car.src.second;
    int ny = y + dy[next_dir];
    int nx = x + dx[next_dir];
    if (is_out(ny, nx))continue;
    if (next_state.visited[ny * MAX_HW + nx]){
      continue;
    }
    next_state.visited[ny * MAX_HW + nx] = true;
    car.src = mp(ny, nx);
    // car.src.first = ny;
    // car.src.second = nx;
  }
  next_state.visited.reset();
  for (const Car &car : cars){
    int y,x;
    y = car.src.first;
    x = car.src.second;
    next_state.visited[y * MAX_HW + x] = true;
  }
  next_state.score = calc_score(next_state.cars, L);
  beams.emplace(next_state);
}

vector<string> restore_path(const State &state){
  vector<string> results;
  vector<vector<pii>> paths;
  /////////////////////////////////
  vector<pii> p;
  for (int i = 0; i < state.cars.size(); i++){
    p.emplace_back(state.cars[i].src);
  }
  paths.emplace_back(p);
  //////////////////////////////////
  for (const State *pos = &state;; pos = pos->parent.get()){
    vector<pii> path;
    if (pos == NULL){
      break;
    }
    const vector<Car>& cars = state.cars;
    for (const Car &car : cars){
      path.emplace_back(car.src);
    }
    paths.push_back(move(path));
  }
  reverse(paths.begin(), paths.end());
  for (int i = 0; i < paths.size() - 1; i++){
    string command = "";
    for (int j = 0; j < paths[i].size(); j++){
      pii pos = paths[i][j];
      pii goal = paths[i + 1][j];
      // cout << pos.first << " " << pos.second << endl;
      // cout << goal.first << " " << goal.second << endl;
      // // cout << endl;
      assert(pos == goal);
      for (int k = 0; k < 5; k++){
        int y = pos.first + dy[k];
        int x = pos.second + dx[k];
        if (y == goal.first and x == goal.second){
          command += DIRS[k];
          break;
        }
      }
    }
    results.emplace_back(command);
  }
  return results;
}
void output_command(const vector<string> &commands){
  cout << commands.size() << endl;
  for (const string &command : commands){
    cout << command << endl;
  }
}
void solve(vector<Car> cars, int limit){
  State root;
  root.cars = cars;
  for (Car &car : cars){
    int y,x;
    y = car.src.first;
    x = car.src.second;
    root.visited[y * MAX_HW + x] = true;
  }
  State best_state = root;
  double best_score = calc_score(root.cars, 0);
  root.score = best_score;
  priority_queue<State> beams[100];
  beams[0].emplace(root);



  for (int depth = 0; depth < 30; depth++){
    for (int iter = 0; iter < 50 and (not beams[depth].empty()); iter++){
      State state = beams[depth].top();
      beams[depth].pop();
      for (int j = 0; j < 50; j++){
        simulate_next_state(state, beams[depth + 1], depth + 1);
      }
    }
  }

  vector<string> commands = restore_path(beams[30].top());
  output_command(commands);
}
int main() {
  vector<Car> cars = input();
  solve(cars, 114514);

  return 0;
}

Submission Info

Judge Result