#901172 (C++17) No.2411 Reverse Directions

提出ソース

結果

問題	No.2411 Reverse Directions
ユーザー	atug tokyo
提出日時	2023-08-12 00:12:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,467 bytes
コンパイル時間	2,559 ms
コンパイル使用メモリ	215,420 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-11-18 20:03:01
合計ジャッジ時間	5,863 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	5 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	7 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	3 ms 6,816 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	3 ms 6,816 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	2 ms 6,816 KB
testcase_20	WA	-
testcase_21	AC	7 ms 6,816 KB
testcase_22	WA	-
testcase_23	AC	3 ms 6,820 KB
testcase_24	WA	-
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	3 ms 6,816 KB
testcase_27	AC	6 ms 6,820 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	14 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
        if (S[i3][j3] == 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;
}

yukicoder

結果

テストケース

ソースコード