結果
| 問題 | No.3738 Right Hamiltonian |
| コンテスト | |
| ユーザー |
 ponjuice
|
| 提出日時 | 2026-09-19 17:32:21 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 13,220 bytes |
| 記録 | |
| コンパイル時間 | 2,827 ms |
| コンパイル使用メモリ | 360,876 KB |
| 実行使用メモリ | 74,496 KB |
| 最終ジャッジ日時 | 2026-09-19 17:32:45 |
| 合計ジャッジ時間 | 13,082 ms |
|
ジャッジサーバーID （参考情報） |
judge5_0 / judge3_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点 | 80 % | WA * 34 RE * 4 |
| 満点 | 20 % | WA * 55 RE * 5 |
| 合計 | 4 * 0% = 0 点 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//高速化
struct ponjuice{ponjuice(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);}}PonJuice;
#define endl '\n' //インタラクティブ問題の時は消す
//型
using ll = long long;
using ld = long double;
// for文
#define overload4(a, b, c, d, e, ...) e
#define rep1(n) for(ll i = 0; i < n; i++)
#define rep2(i, n) for(ll i = 0; i < n; i++)
#define rep3(i, a, b) for(ll i = a; i < b; i++)
#define rep4(i, a, b, step) for(ll i = a; i < b; i+= step)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(n) for(ll i = n-1; i >= 0; i--)
#define per2(i, n) for(ll i = n-1; i >= 0; i--)
#define per3(i, a, b) for(ll i = b-1; i >= a; i--)
#define per4(i, a, b, step) for(ll i = b-1; i >= a; i-= step)
#define per(...) overload4(__VA_ARGS__, per4, per3, per2, per1)(__VA_ARGS__)
//関数
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template<class S, class T>inline bool chmax(S& a, T b){return a < b && ( a = b , true);}
template<class S, class T>inline bool chmin(S& a, T b){return a > b && ( a = b , true);}
//定数
constexpr ll mod = 998244353;
constexpr ll minf=-(1<<29);
constexpr ll inf=(1<<29);
constexpr ll MINF=-(1LL<<60);
constexpr ll INF=(1LL<<60);
const int dx[4] ={-1, 0, 1, 0};
const int dy[4] ={ 0, 1, 0,-1};
const int dx8[8] ={-1,-1,-1, 0, 1, 1, 1, 0};
const int dy8[8] ={-1, 0, 1, 1, 1, 0,-1,-1};
void solve();
int main() {
int t = 1;
// cin >> t;
while(t--)solve();
}
struct Ans {
pair<ll,ll> S = {0,0}, D = {0, 0};
string command;
bool ok = 0;
};
Ans sol(vector<string> s) {
for(auto x: s) cout << x << endl;
int h = s.size();
int w = s[0].size();
vector<vector<int>> u(h, vector<int>(w, 0)),d(h, vector<int>(w, 0)),r(h, vector<int>(w, 0)),l(h, vector<int>(w, 0));
rep(i,0,h) {
rep(j,0,w) {
// u, l
if(i && s[i-1][j]=='.' && s[i][j]=='.') chmax(u[i][j], u[i-1][j]+1);
if(j && s[i][j-1]=='.' && s[i][j]=='.') chmax(l[i][j], l[i][j-1]+1);
}
}
per(i,0,h){
per(j,0,w) {
if(i<h-1 && s[i+1][j]=='.' && s[i][j]=='.') chmax(d[i][j], d[i+1][j]+1);
if(j<w-1 && s[i][j+1]=='.' && s[i][j]=='.') chmax(r[i][j], r[i][j+1]+1);
}
}
ll cnt = 0;
rep(i,0,h)rep(j,0,w) if(s[i][j]=='.') cnt++;
ll L = 0, R = cnt;
rep(i,0,w-1) {
rep(j,0,h) {
if(s[j][i] == '.') L++,R--;
}
per(j,0,h) {
if(s[j][i]=='.' && s[j][i+1] == '.') {
// 探索
bool ok = true;
// l 右回り
{
ll ds=j-1,us=0,ls=0,rs=i;
ll count = 1;
ll x = j, y = i;
int dir = 3; // デクリメントで回す
if(l[x][y] == 0) dir = 0;
while(true) {
if(dir==0){ // 上
int nx = max(us, x-u[x][y]);
int ny = y;
if(nx == x) break;
us = nx+1;
count += abs(x - nx);
x = nx;
y = ny;
}
if(dir==1){ // 右
int nx = x;
int ny = min(rs, y+r[x][y]);
if(ny == y) break;
rs = ny-1;
count += abs(y - ny);
x = nx;
y = ny;
}
if(dir==2){ // した
int nx = min(ds, x+d[x][y]);
int ny = y;
if(nx == x) break;
ds = nx-1;
count += abs(x - nx);
x = nx;
y = ny;
}
if(dir==3){ // 左
int nx = x;
int ny = max(ls, y-l[x][y]);
if(ny == y) break;
ls = ny+1;
count += abs(y - ny);
x = nx;
y = ny;
}
dir = (dir+1)%4;
// cout << x << " " << y << " " << dir << " " << l[x][y] << endl;
}
if(count != L) ok = false;
// cout << L << " " << count << " , ";
}
// r 左回り
{
ll ds=j-1,us=0,ls=i+2,rs=w;
ll count = 1;
ll x = j, y = i+1;
int dir = 1;
if(r[x][y] == 0) dir = 0;
while(true) {
if(dir==0){ // 上
int nx = max(us, x-u[x][y]);
int ny = y;
if(nx == x) break;
us = nx+1;
count += abs(x - nx);
x = nx;
y = ny;
}
if(dir==1){ // 右
int nx = x;
int ny = min(rs, y+r[x][y]);
if(ny == y) break;
rs = ny-1;
count += abs(y - ny);
x = nx;
y = ny;
}
if(dir==2){ // した
int nx = min(ds, x+d[x][y]);
int ny = y;
if(nx == x) break;
ds = nx-1;
count += abs(x - nx);
x = nx;
y = ny;
}
if(dir==3){ // 左
int nx = x;
int ny = max(ls, y-l[x][y]);
if(ny == y) break;
ls = ny+1;
count += abs(y - ny);
x = nx;
y = ny;
}
dir = (dir+3)%4;
}
// cout << R << " " << count << endl;
if(count != R) ok = false;
}
if(ok) {
// 解の作成
Ans ans;
ans.ok = true;
// r 左回り
{
ll ds=j-1,us=0,ls=i+2,rs=w;
ll count = 1;
ll x = j, y = i+1;
int dir = 1;
if(r[x][y] == 0) {
dir = 0;
ans.command += "R";
}else {
ans.command += "F";
}
while(true) {
if(dir==0){ // 上
int nx = max(us, x-u[x][y]);
int ny = y;
if(nx == x) break;
us = nx+1;
ans.command += string(abs(x - nx)-1, 'F');
ans.command += "R";
x = nx;
y = ny;
}
if(dir==1){ // 右
int nx = x;
int ny = min(rs, y+r[x][y]);
if(ny == y) break;
rs = ny-1;
ans.command += string(abs(y - ny)-1, 'F');
ans.command += "R";
x = nx;
y = ny;
}
if(dir==2){ // した
int nx = min(ds, x+d[x][y]);
int ny = y;
if(nx == x) break;
ds = nx-1;
ans.command += string(abs(x - nx)-1, 'F');
ans.command += "R";
x = nx;
y = ny;
}
if(dir==3){ // 左
int nx = x;
int ny = max(ls, y-l[x][y]);
if(ny == y) break;
ls = ny+1;
ans.command += string(abs(y - ny)-1, 'F');
ans.command += "R";
x = nx;
y = ny;
}
dir = (dir+3)%4;
}
reverse(all(ans.command));
ans.S = {x, y};
ans.D = {-dx[dir], -dy[dir]};
}
{
ll ds=j-1,us=0,ls=0,rs=i;
ll count = 1;
ll x = j, y = i;
int dir = 3; // デクリメントで回す
int ch = -1;
if(l[x][y] == 0) {
dir = 0;
ans.command += "R";
}else{
ans.command += "F";
}
while(true) {
if(dir==0){ // 上
int nx = max(us, x-u[x][y]);
int ny = y;
if(nx == x) break;
us = nx+1;
ans.command += string(abs(x - nx)-1, 'F');
x = nx;
y = ny;
}
if(dir==1){ // 右
int nx = x;
int ny = min(rs, y+r[x][y]);
if(ny == y) break;
rs = ny-1;
ans.command += string(abs(y - ny)-1, 'F');
x = nx;
y = ny;
}
if(dir==2){ // した
int nx = min(ds, x+d[x][y]);
int ny = y;
if(nx == x) break;
ds = nx-1;
ans.command += string(abs(x - nx)-1, 'F');
x = nx;
y = ny;
}
if(dir==3){ // 左
int nx = x;
int ny = max(ls, y-l[x][y]);
if(ny == y) break;
ls = ny+1;
ans.command += string(abs(y - ny)-1, 'F');
x = nx;
y = ny;
}
ans.command += "R";
dir = (dir+1)%4;
}
ans.command.pop_back();
}
return ans;
}
break;
}
}
}
return Ans();
}
void solve(){
int h,w;
cin >> h >> w;
vector<string> s(h);
rep(i,0,h) cin >> s[i];
Ans ans;
rep(i,0,4) {
if(ans.ok == false) ans = sol(s);
{ // rotate ans ans map
vector<string> nx(w, string(h,'?'));
rep(i,0,h) {
rep(j,0,w) {
nx[j][h-1-i] = s[i][j];
}
}
s.swap(nx);
pair<ll,ll> nxa = {ans.S.second, h-1-ans.S.first};
ans.S = nxa;
pair<ll,ll> nxd = {ans.D.second, -ans.D.first};
ans.D = nxd;
swap(h,w);
}
}
if(ans.ok) {
cout << ans.S.first+1 << " " << ans.S.second+1 << " ";
if(ans.D==pair<ll,ll>{1, 0}) cout << "D" << endl;
if(ans.D==pair<ll,ll>{-1, 0}) cout << "U" << endl;
if(ans.D==pair<ll,ll>{0, 1}) cout << "R" << endl;
if(ans.D==pair<ll,ll>{0, -1}) cout << "L" << endl;
cout << ans.command.size() << endl;
cout << ans.command << endl;
}else{
cout << -1 << endl;
}
}