結果
| 問題 | No.2411 Reverse Directions |
| ユーザー |
 milanis48663220
|
| 提出日時 | 2023-08-11 23:39:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 26 ms / 2,000 ms |
| コード長 | 5,728 bytes |
| コンパイル時間 | 1,497 ms |
| コンパイル使用メモリ | 134,804 KB |
| 最終ジャッジ日時 | 2025-02-16 02:16:57 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <deque>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;template<typename T>vector<vector<T>> vec2d(int n, int m, T v){return vector<vector<T>>(n, vector<T>(m, v));}template<typename T>vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));}template<typename T>void print_vector(vector<T> v, char delimiter=' '){if(v.empty()) {cout << endl;return;}for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;cout << v.back() << endl;}using P = pair<int, int>;using T = tuple<int, int, int>;int dx[] = {1, -1, 0, 0};int dy[] = {0, 0, 1, -1};pair<vector<vector<int>>, vector<vector<P>>> calc_dist(vector<string> s, int sx, int sy){int h = s.size(), w = s[0].size();queue<P> que;auto dist = vec2d(h, w, -1);auto pre = vec2d(h, w, P(-1, -1));auto set_dist = [&](int i, int j, int d){if(dist[i][j] == -1){que.push({i, j});dist[i][j] = d;return true;}return false;};auto in_field = [&](int x, int y){return 0 <= x && x < h && 0 <= y && y < w;};set_dist(sx, sy, 0);while(!que.empty()){auto [x, y] = que.front(); que.pop();for(int k = 0; k < 4; k++) {int xx = x+dx[k];int yy = y+dy[k];if(!in_field(xx, yy)) continue;if(s[xx][yy] != '.') continue;if(set_dist(xx, yy, dist[x][y]+1)){pre[xx][yy] = {x, y};}}}return make_pair(dist, pre);}string inv(string s){string ans;for(char c: s){if(c == 'L') ans += 'R';if(c == 'R') ans += 'L';if(c == 'D') ans += 'U';if(c == 'U') ans += 'D';}return ans;}string make_path(int x, int y, vector<vector<P>> pre){string ans;while(true){auto [xx, yy] = pre[x][y];if(xx == -1){assert(yy == -1);break;}if(x == xx+1){ans += 'D';}else if(x == xx-1){ans += 'U';}else if(y == yy+1){ans += 'R';}else{assert(y == yy-1);ans += 'L';}x = xx;y = yy;}reverse(ans.begin(), ans.end());return ans;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;int h, w, k, l, r; cin >> h >> w >> k >> l >> r; l--;vector<string> s(h);for(int i = 0; i < h; i++) cin >> s[i];auto fx = [&](int i, int j){if(i-1 >= 0 && i+1 < h){if(s[i-1][j] == '.' && s[i][j] == '.' && s[i+1][j] == '.') return true;}return false;};auto fy = [&](int i, int j){if(j-1 >= 0 && j+1 < w){if(s[i][j-1] == '.' && s[i][j] == '.' && s[i][j+1] == '.') return true;}return false;};auto f = [&](int i, int j){return fx(i, j) || fy(i, j);};if(r%2 != l%2){cout << "No" << endl;return 0;}if((h+w-2)%2 != (k-(r-l))%2){cout << "No" << endl;return 0;}if((h+w-2) > k-(r-l)){cout << "No" << endl;return 0;}auto in_field = [&](int x, int y){return 0 <= x && x < h && 0 <= y && y < w;};auto verify = [&](string t, int xt, int yt){int x = 0, y = 0;for(char c: t){if(c == 'D') x++;if(c == 'U') x--;if(c == 'L') y--;if(c == 'R') y++;// assert(in_field(x, y));assert(s[x][y] == '.');}};auto [ds, pre_s] = calc_dist(s, 0, 0);auto [dt, pre_t] = calc_dist(s, h-1, w-1);for(int i = 0; i < h; i++){for(int j = 0; j < w; j++){if(ds[i][j] == -1 || dt[i][j] == -1){continue;}if(!f(i, j)) continue;if((i+j)%2 != l%2) continue;if(ds[i][j] > l) continue;if(dt[i][j] > k-r) continue;int extra = k-(ds[i][j]+dt[i][j]);string ans = make_path(i, j, pre_s);auto ans_inv = ans;verify(ans, i, j);// cout << i << ' ' << j << endl;if(fx(i, j)){while(extra){ans += "DU";ans_inv += "UD";extra-=2;}}else{assert(fy(i, j));while(extra){ans += "LR";ans_inv += "RL";extra-=2;}}assert(ans.size() >= r);auto tail = inv(make_path(i, j, pre_t));reverse(tail.begin(), tail.end());ans += tail;ans_inv += tail;cout << "Yes" << endl;cout << ans << endl;assert(ans.size() == k);// verify(ans_inv);return 0;}}cout << "No" << endl;return 0;}