結果
問題 | No.2411 Reverse Directions |
ユーザー |
![]() |
提出日時 | 2023-08-11 22:22:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,287 bytes |
コンパイル時間 | 2,150 ms |
コンパイル使用メモリ | 211,732 KB |
最終ジャッジ日時 | 2025-02-16 01:38:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 TLE * 1 -- * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long signed main(){ int H,W,K,L,R; cin>>H>>W>>K>>L>>R; vector<vector<char>> S(H,vector<char>(W)); for(int i=0;i<H;i++)for(int j=0;j<W;j++) cin>>S[i][j]; vector<vector<int>> G(H*W); for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(S[i][j] == '#') continue; if(i != 0 && S[i-1][j] == '.') G[i*W+j].push_back(i*W+j-W); if(i != H-1 && S[i+1][j] == '.') G[i*W+j].push_back(i*W+j+W); if(j != 0 && S[i][j-1] == '.') G[i*W+j].push_back(i*W+j-1); if(j != W-1 && S[i][j+1] == '.') G[i*W+j].push_back(i*W+j+1); } vector<int> dist(H*W,1e18); dist[0] = 0; queue<int> q; q.push(0); while(!q.empty()){ int pos = q.front(); q.pop(); for(int x:G[pos]){ if(dist[x] != 1e18) continue; dist[x] = dist[pos] + 1; q.push(x); } } if(dist[H*W-1] == 1e18 || dist[H*W-1]%2 != K%2 || (R-L)%2 == 0){ cout<<"No"<<endl; return 0; } for(int i=0;i<H;i++)for(int j=0;j<W;j++){ if(S[i][j] == '#' || dist[i*W+j] >= L || dist[H*W-1]-dist[i*W+j] > K-R || dist[i*W+j]%2 == L%2 || (dist[H*W-1]-dist[i*W+j])%2 != (K-R)%2 || dist[i*W+j] == 1e18) continue; bool a = (i != 0 && i != H-1 && S[i-1][j] == '.' && S[i+1][j] == '.'); bool b = (j != 0 && j != W-1 && S[i][j-1] == '.' && S[i][j+1] == '.'); if(a){ cout<<"Yes"<<endl; string s = "", t = "", ans = ""; int now = i*W+j; while(now != 0){ for(int x:G[now]){ if(dist[x]+1 == dist[now]){ if(x == now-1) s += 'R'; if(x == now+1) s += 'L'; if(x == now-W) s += 'D'; if(x == now+W) s += 'U'; now = x; break; } } } now = H*W-1; vector<int> distt(H*W,1e18); distt[i*W+j] = 0; q.push(i*W+j); while(!q.empty()){ int pos = q.front(); q.pop(); for(int x:G[pos]){ if(distt[x] != 1e18) continue; distt[x] = distt[pos] + 1; q.push(x); } } while(now != i*W+j){ for(int x:G[now]){ if(distt[x]+1 == distt[now]){ if(x == now-1) t += 'R'; if(x == now+1) t += 'L'; if(x == now-W) t += 'D'; if(x == now+W) t += 'U'; now = x; break; } } } for(int k=dist[i*W+j]+1;k<K-(dist[H*W-1]-dist[i*W+j]);k+=2){ s += 'L'; s += 'R'; } ans = s+t; cout<<ans<<endl; return 0; } if(b){ cout<<"Yes"<<endl; string s = "", t = "", ans = ""; int now = i*W+j; while(now != 0){ for(int x:G[now]){ if(dist[x]+1 == dist[now]){ if(x == now-1) s += 'R'; if(x == now+1) s += 'L'; if(x == now-W) s += 'D'; if(x == now+W) s += 'U'; now = x; break; } } } now = H*W-1; vector<int> distt(H*W,1e18); distt[i*W+j] = 0; q.push(i*W+j); while(!q.empty()){ int pos = q.front(); q.pop(); for(int x:G[pos]){ if(distt[x] != 1e18) continue; distt[x] = distt[pos] + 1; q.push(x); } } while(now != i*W+j){ for(int x:G[now]){ if(distt[x]+1 != distt[now]){ if(x == now-1) t += 'R'; if(x == now+1) t += 'L'; if(x == now-W) t += 'D'; if(x == now+W) t += 'U'; now = x; break; } } } for(int k=dist[i*W+j]+1;k<K-(dist[H*W-1]-dist[i*W+j]);k+=2){ s += 'U'; s += 'D'; } ans = s+t; cout<<ans<<endl; return 0; } } cout<<"No"<<endl; }