Submission #1176671

---

Source Code Expand

#include <bits/stdc++.h>

struct Point {
  long r, c;
  Point() : r(-1), c(-1) {}
  Point(long r_, long c_) : r(r_), c(c_) {}
  bool inrange() {
    return 1 <= r and r <= 30 and 1 <= c and c <= 30;
  }
};
Point operator + (Point x, Point y) {
  return Point(x.r + y.r, x.c + y.c);
}
Point d4[] = {
  Point(1, 0),
  Point(0, 1),
  Point(-1, 0),
  Point(0, -1)
};
char c4[] = "DRUL-";

struct Car {
  Point s, d;
  Car() {}
  Car(Point s_, Point d_) : s(s_), d(d_) {}
  long dist() {
    return std::abs(s.r - d.r) + std::abs(s.c - d.c);
  }
};

void solve(long h, long w, long k, long t, std::array<Car, 450> cs) {
  std::vector<std::string> answers;
  for(long i = 0; i < 10000-1; ++i) {
    bool reserved[32][32] = {{}};
    for(long j = 0; j < 450; ++j) {
      reserved[cs[j].s.r][cs[j].s.c] = true;
    }
    std::string ans;
    ans.resize(450);
    std::vector<long> random;
    for(long j = 0; j < 450; ++j) {
      random.push_back(j);
    }
    std::random_shuffle(random.begin(), random.end());    
    for(long jj = 0; jj < 450; ++jj) {
      long j = random[jj];
      long best = (1 << 28);
      long bestkk = 4;
      for(long kk : {i%4, (i+1)%4, (i+2)%4, (i+3)%4}) {
        Point next = cs[j].s + d4[kk];
        Car nextC = Car(next, cs[j].d);
        if( reserved[next.r][next.c] ) continue;
        if( not next.inrange() ) continue;
        if( nextC.dist() < best ) {
          best = nextC.dist();
          bestkk = kk;
        }
      }
      ans[j] = c4[bestkk];
      Point next = cs[j].s + d4[bestkk];
      reserved[next.r][next.c] = true;
      cs[j].s = next;
    }
    answers.push_back(ans);
    long maxDiff = 0;
    for(long j = 0; j < 450; ++j) {
      maxDiff = std::max(maxDiff, cs[j].dist());
    }
    if( maxDiff <= 6 ) break;
  }
  {
    bool reserved[32][32] = {{}};
    for(long j = 0; j < 450; ++j) {
      reserved[cs[j].s.r][cs[j].s.c] = true;
    }
    std::string ans;
    ans.resize(450);
    for(long j = 0; j < 450; ++j) {
      long best = cs[j].dist();
      long bestkk = 4;
      for(long kk = 0; kk < 4; ++kk) {
        Point next = cs[j].s + d4[kk];
        Car nextC = Car(next, cs[j].d);
        if( reserved[next.r][next.c] ) continue;
        if( not next.inrange() ) continue;
        if( nextC.dist() < best ) {
          best = nextC.dist();
          bestkk = kk;
        }
      }
      ans[j] = c4[bestkk];
      Point next = cs[j].s + d4[bestkk];
      reserved[next.r][next.c] = true;
      cs[j].s = next;
    }
    answers.push_back(ans);
  }
  
  

  printf("%ld\n", (long)answers.size());
  for(std::string& str : answers) {
    printf("%s\n", str.c_str());
  }
}

int main() {
  long h, w, k, t;
  std::array<Car, 450> cs;
  scanf("%ld %ld %ld %ld", &h, &w, &k, &t);
  for(long i = 0; i < k; ++i) {
    long a, b, c, d;
    scanf("%ld %ld %ld %ld", &a, &b, &c, &d); 
    cs[i] = Car(Point(a, b), Point(c, d));
  }
  solve(h, w, k, t, cs);
  
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:110:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%ld %ld %ld %ld", &h, &w, &k, &t);
                                           ^
./Main.cpp:113:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%ld %ld %ld %ld", &a, &b, &c, &d); 
                                             ^

Judge Result