結果

問題 No.2411 Reverse Directions
コンテスト
ユーザー atug tokyo
提出日時 2023-08-11 23:58:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,429 bytes
コンパイル時間 2,325 ms
コンパイル使用メモリ 209,436 KB
最終ジャッジ日時 2025-02-16 02:27:53
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 15
権限があれば一括ダウンロードができます

ソースコード

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