結果
問題 | No.2411 Reverse Directions |
ユーザー |
![]() |
提出日時 | 2023-08-11 22:00:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 2,606 bytes |
コンパイル時間 | 4,289 ms |
コンパイル使用メモリ | 259,320 KB |
最終ジャッジ日時 | 2025-02-16 01:23:26 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001void ng(){cout<<"No"<<endl;exit(0);}vector<int> dx = {1,-1,0,0},dy = {0,0,1,-1};string s = "DURL";void bfs(vector<vector<int>> &d,vector<string> &S,int sx,int sy){int h = d.size(),w = d[0].size();d[sx][sy] = 0;queue<pair<int,int>> Q;Q.emplace(sx,sy);while(Q.size()>0){int x = Q.front().first;int y = Q.front().second;Q.pop();rep(i,4){int xx = x + dx[i],yy = y+dy[i];if(xx<0||xx>=h||yy<0||yy>=w)continue;if(S[xx][yy]=='#')continue;if(d[xx][yy]!=Inf32)continue;d[xx][yy] = d[x][y]+1;Q.emplace(xx,yy);}}}int main(){int h,w;cin>>h>>w;int K;cin>>K;int L,R;cin>>L>>R;vector<string> S(h);rep(i,h)cin>>S[i];if((R-L+1)%2==1)ng();if((h+w)%2 != K%2)ng();// cout<<'a'<<endl;vector d0(h,vector<int>(w,Inf32));auto d1 = d0;bfs(d0,S,0,0);//cout<<'b'<<endl;bfs(d1,S,h-1,w-1);//cout<<'c'<<endl;rep(i,h){rep(j,w){if(d0[i][j]<=L-1 && d1[i][j]<=K-R && d0[i][j]%2==(L-1)%2){int ok = -1;for(int k=0;k<4;k+=2){bool f = true;rep(l,2){int t = k + l;int xx = i + dx[t],yy = j+dy[t];if(xx<0||xx>=h||yy<0||yy>=w){f = false;break;}if(S[xx][yy]=='#')f = false;}if(f)ok = k;}if(ok==-1)continue;cout<<"Yes"<<endl;string temp = "";int cx = i,cy = j;while(cx!=0 || cy!=0){//cout<<cx<<','<<cy<<endl;rep(k,4){//cout<<k<<endl;int xx = cx + dx[k],yy = cy + dy[k];if(xx<0||xx>=h||yy<0||yy>=w)continue;if(d0[xx][yy]+1!=d0[cx][cy])continue;//cout<<k<<endl;temp += s[k^1];//cout<<k<<endl;cx = xx,cy = yy;//cout<<k<<endl;break;}//cout<<cx<<','<<cy<<endl;}reverse(temp.begin(),temp.end());while(temp.size()!=R){temp += s[ok];temp += s[ok^1];}cx = i,cy = j;int last = 0;while(cx!=h-1 || cy!=w-1){//cout<<cx<<",,"<<cy<<endl;rep(k,4){int xx = cx + dx[k],yy = cy + dy[k];if(xx<0||xx>=h||yy<0||yy>=w)continue;if(d1[xx][yy]+1!=d1[cx][cy])continue;temp += s[k];cx = xx,cy = yy;last = k;break;}}while(temp.size()!=K){temp += s[last^1];temp += s[last];}cout<<temp<<endl;return 0;}}}ng();return 0;}