結果

問題 No.2411 Reverse Directions
ユーザー atug tokyoatug tokyo
提出日時 2023-08-11 23:58:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,429 bytes
コンパイル時間 2,556 ms
コンパイル使用メモリ 215,328 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-11-18 19:50:01
合計ジャッジ時間 5,303 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 5 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 3 ms
5,248 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 3 ms
5,248 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
5,248 KB
testcase_20 WA -
testcase_21 AC 8 ms
5,248 KB
testcase_22 WA -
testcase_23 AC 3 ms
5,248 KB
testcase_24 WA -
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 6 ms
5,248 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 14 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

using Pair = pair<int, int>;
using Tuple = tuple<int, int, int>;
using VI1 = vector<int>;
using VI2 = vector<VI1>;
using VL1 = vector<ll>;
using VL2 = vector<VL1>;
using VD1 = vector<ld>;
using VD2 = vector<VD1>;
using VB1 = vector<bool>;
using VB2 = vector<VB1>;
using VP1 = vector<Pair>;
using VP2 = vector<VP1>;
using VT1 = vector<Tuple>;
using VT2 = vector<VT1>;

using Queue = queue<Pair>;
using DQ = deque<int>;
using PQ = priority_queue<int, vector<int>, greater<int>>;
using Table = VI2;
using Graph = VI2;

/** io */
template <typename T>
std::vector<T> input_vec(int N);
template <typename T>
void output_row(std::vector<T> &row);
template <typename T>
void output_col(std::vector<T> &col);
void outputYesNo(bool yes, const string &Yes = "Yes", const string &No = "No");
/** minmax */
template <typename T>
bool chmin(T &a, T b);
template <typename T>
bool chmax(T &a, T b);

using Cell = int;
using Row = vector<Cell>;
using Grid = vector<Row>;

Cell read_cell() {
  Cell cell;
  char c;
  cin >> c;
  cell = (c == '#') ? 1 : 0;
  return cell;
}

Grid read_grid(int H, int W) {
  Grid grid(H, Row(W));
  for (auto &row : grid) {
    for (auto &cell : row) {
      cell = read_cell();
    }
  }
  return grid;
}

bool is_out(int H, int W, int x, int y) {
  if (x < 0 || H <= x) return true;
  if (y < 0 || W <= y) return true;
  return false;
}

Grid rotate(Grid &org) {
  int H = org.size();
  int W = org.front().size();
  Grid rotated(W, Row(H));
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      rotated[W - 1 - j][i] = org[i][j];
    }
  }
  return rotated;
}

const vector<int> dx{0, 0, -1, 1}, dy{-1, 1, 0, 0};
const string LRUD = "LRUD";

const int INF = 1001001001;

Grid calc_cost(int H, int W, Grid &S, int sx, int sy) {
  Grid cost(H, Row(W, INF));
  Queue que;
  cost[sx][sy] = 0;
  que.emplace(sx, sy);
  while (que.size()) {
    auto [x1, y1] = que.front();
    que.pop();
    for (int i = 0; i < 4; ++i) {
      auto x2 = x1 + dx[i], y2 = y1 + dy[i];
      if (is_out(H, W, x2, y2)) continue;
      if (S[x2][y2] == 1) continue;
      if (chmin(cost[x2][y2], cost[x1][y1] + 1)) {
        que.emplace(x2, y2);
      }
    }
  }
  return cost;
}

string calc_route(int H, int W, Grid &S, Grid &cost, int sx, int sy) {
  string route;
  int len = cost[sx][sy];
  for (int i = 0, x1 = sx, y1 = sy; i < len; ++i) {
    for (int j = 0; j < 4; ++j) {
      auto x2 = x1 + dx[j], y2 = y1 + dy[j];
      if (is_out(H, W, x2, y2)) continue;
      if (S[x2][y2] == 1) continue;
      if (cost[x2][y2] == cost[x1][y1] - 1) {
        route += LRUD[j];
        x1 = x2, y1 = y2;
        break;
      }
    }
  }
  return route;
}

void convert(string &T1) {
  reverse(T1.begin(), T1.end());
  int len = T1.size();
  for (int i = 0; i < len; ++i) {
    auto T1i = T1.at(i);
    if (T1i == 'L') T1[i] = 'R';
    if (T1i == 'R') T1[i] = 'L';
    if (T1i == 'U') T1[i] = 'D';
    if (T1i == 'D') T1[i] = 'U';
  }
  return;
}

auto solve(string &T) {
  int H, W, K, L, R;
  cin >> H >> W >> K >> L >> R;
  --L;
  auto S = read_grid(H, W);
  if ((R - L) % 2 == 1) return false;
  auto cost1 = calc_cost(H, W, S, 0, 0);
  auto cost2 = calc_cost(H, W, S, H - 1, W - 1);
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (S[i][j] == 1) continue;
      if (cost1[i][j] > L || (L - cost1[i][j]) % 2 != 0) continue;
      if (cost2[i][j] > K - R || (K - R - cost2[i][j]) % 2 != 0) continue;
      int k0 = -1;
      for (int k = 0; k0 == -1 && k < 4; k += 2) {
        auto i2 = i + dx[k], j2 = j + dy[k];
        auto i3 = i - dx[k], j3 = j - dy[k];
        if (is_out(H, W, i2, j2)) continue;
        if (is_out(H, W, i3, j3)) continue;
        if (S[i2][j2] == 1) continue;
        k0 = k;
      }
      if (k0 == -1) continue;
      auto T1 = calc_route(H, W, S, cost1, i, j);
      auto T2 = calc_route(H, W, S, cost2, i, j);
      convert(T1);
      for (int k = 0; k < R - L; ++k) {
        T1.push_back(LRUD.at(k0 + k % 2));
      }
      T = T1 + T2;
      return true;
    }
  }
  return false;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    string T;
    auto result = solve(T);
    outputYesNo(result);
    if (result) {
      cout << T << '\n';
    }
    // output_row(result);
    // output_col(result);
    // outputYesNo(result, "Yes", "No");
  }
}

/** @note 使用頻度が高く毎回貼付するのが面倒なライブラリを実装しておく。*/

template <typename T>
std::vector<T> input_vec(int N) {
  std::vector<T> v(N);
  for (auto &vi : v) {
    cin >> vi;
  }
  return v;
}

void outputYesNo(bool yes, const string &Yes, const string &No) {
  if (yes)
    cout << Yes << '\n';
  else
    cout << No << '\n';
}

template <typename T>
void output_row(std::vector<T> &row) {
  int N = row.size();
  for (int i = 0; i < N; ++i) {
    if (i > 0) cout << ' ';
    cout << row.at(i);
  }
  cout << '\n';
}

template <typename T>
void output_col(std::vector<T> &col) {
  int N = col.size();
  for (int i = 0; i < N; ++i) {
    cout << col.at(i) << '\n';
  }
}

template <typename T>
bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T>
bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
0