結果
問題 | No.2411 Reverse Directions |
ユーザー |
|
提出日時 | 2023-08-11 23:33:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 4,811 bytes |
コンパイル時間 | 2,211 ms |
コンパイル使用メモリ | 213,604 KB |
最終ジャッジ日時 | 2025-02-16 02:13:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;typedef pair<ll, ll> Pll;typedef pair<ld, ld> Pdd;template<typename T>using MaxHeap = priority_queue<T>;template<typename T>using MinHeap = priority_queue<T, vector<T>, greater<T>>;#define REP(i, n) for(int i = 0; i < n; i++)#define REPR(i, n) for(int i = n; i >= 0; i--)#define FOR(i, m, n) for(int i = m; i < n; i++)#define FORR(i, m, n) for(int i = m; i >= n; i--)#define INF (ll)1e17#define ALL(v) v.begin(), v.end()#define SZ(x) ((ll)(x).size())#define bit(n) (1LL<<(n))#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );#define cauto const auto&#define cdebug if (debug_mode) cerr#define dump(x) if (debug_mode) cerr << #x << " = " << (x) << "\t";#define SP << " " <<#define TB << "\t" <<#ifdef _LOCALbool debug_mode = true;#elsebool debug_mode = false;#endifint main(){ll H, W, K, L, R;cin >> H >> W >> K >> L >> R;vector<string> board(H);REP(i, H) cin >> board[i];if ((R - L) % 2 == 0 || (H + W - K) % 2 != 0 || (K - (R-L+1)) < (H+W-2)) {cout << "No" << endl;return 0;}vector<vector<ll>> dist(H, vector<ll>(W, INF));set<Pll> ps;deque<Pll> Q;Q.push_back({0, 0});dist[0][0] = 0;ll dy[] = {0, 1, 0, -1};ll dx[] = {1, 0, -1, 0};ll sum = 0;while (!Q.empty()) {Pll p = Q.front(); Q.pop_front();ll y = p.first, x = p.second;sum++;REP(k, 4) {ll ny = y + dy[k], nx = x + dx[k];if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;if (board[ny][nx] == '#') continue;if (dist[ny][nx] <= dist[y][x] + 1) continue;dist[ny][nx] = dist[y][x] + 1;Q.push_back({ny, nx});if ((dist[y][x] - L) % 2 == 0 || dist[y][x] > L) continue;ll ny2 = y - dy[k], nx2 = x - dx[k];if (ny2 < 0 || ny2 >= H || nx2 < 0 || nx2 >= W) continue;if (board[ny2][nx2] == '#') continue;ps.insert({y, x});}}cdebug << sum << endl;vector<vector<ll>> dist2(H, vector<ll>(W, INF));deque<Pll> Q2;Q2.push_back({H-1, W-1});dist2[H-1][W-1] = 0;while (!Q2.empty()) {Pll p = Q2.front(); Q2.pop_front();ll y = p.first, x = p.second;REP(k, 4) {ll ny = y + dy[k], nx = x + dx[k];if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;if (board[ny][nx] == '#') continue;if (dist2[ny][nx] <= dist2[y][x] + 1) continue;dist2[ny][nx] = dist2[y][x] + 1;Q2.push_back({ny, nx});}}for (auto p : ps) {ll y = p.first, x = p.second;cdebug << y SP x << endl;if (dist2[y][x] <= K - R) {string ans = "";ll d = dist2[y][x];// 経路復元while (d > 0) {REP(k, 4) {ll ny = y + dy[k], nx = x + dx[k];if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;if (board[ny][nx] == '#') continue;if (dist2[ny][nx] != d - 1) continue;ans += "RDLU"[k];y = ny, x = nx;d--;break;}}reverse(ALL(ans));y = p.first;x = p.second;REP(k, 2) {ll ny = y + dy[k], nx = x + dx[k];ll ny2 = y - dy[k], nx2 = x - dx[k];cdebug << ny SP nx SP ny2 SP nx2 << endl;if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;if (ny2 < 0 || ny2 >= H || nx2 < 0 || nx2 >= W) continue;if (board[ny][nx] == '#') continue;if (board[ny2][nx2] == '#') continue;REP(i, (K-dist[y][x]-dist2[y][x])/2) {ans += "RDLU"[k];ans += "RDLU"[k+2];}break;}d = dist[y][x];while (d > 0) {REP(k, 4) {ll ny = y + dy[k], nx = x + dx[k];if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;if (board[ny][nx] == '#') continue;if (dist[ny][nx] != d - 1) continue;ans += "LURD"[k];y = ny, x = nx;d--;break;}}reverse(ALL(ans));cout << "Yes" << endl;cout << ans << endl;return 0;}}cdebug << "unreachable" << endl;cout << "No" << endl;return 0;}