結果

問題 No.3738 Right Hamiltonian
コンテスト
ユーザー 👑 Nachia
提出日時 2026-09-19 15:01:38
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
RE  
実行時間 -
コード長 2,610 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 588 ms
コンパイル使用メモリ 105,780 KB
実行使用メモリ 24,968 KB
最終ジャッジ日時 2026-09-19 15:01:48
合計ジャッジ時間 7,888 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点 80 % AC * 17 WA * 14 RE * 7
満点 20 % AC * 26 WA * 25 RE * 9
合計 4 * 0% = 0 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

struct Ans {
  pair<ll,ll> S = {0,0}, T = {0,0};
  string command;
  bool ok = 0;
};

ll dx[4] = {0,1,0,-1};
ll dy[4] = {-1,0,1,0};

Ans solve(ll H, ll W, V<string> A){
  ll yp = -1, xp = -1, d = 0;;
  Ans ans;
  for(ll x=W-1; x>=0; x--) REP(y,H) if(A[y][x] == '.' && y > 0 && A[y-1][x] == '.'){ yp = y; xp = x; }
  auto onBoard = [&](ll y, ll x){ return 0 <= y && y < H && 0 <= x && x < W; };
  auto test = [&](ll y, ll x, ll d){
    y += dy[d]; x += dx[d];
    if(!onBoard(y,x)) return '#';
    return A[y][x];
  };
  ans.S = {yp, xp};
  // cout<< "solve" << endl;
  // for(auto& a : A) cout << a << endl;
  while(1){
    // cout << "y = " << yp << " , x = " << xp << " , d = " << d << endl;
    A[yp][xp] = '#';
    if(test(yp, xp, d) == '.'){ ans.command.push_back('F'); }
    else if(test(yp, xp, (d+1)%4) == '.'){ ans.command.push_back('R'); d = (d+1)%4; }
    else{ break; }
    yp += dy[d];
    xp += dx[d];
  }
  REP(y,H) REP(x,W) if(A[y][x] != '#') return ans;
  // cout << "OK" << endl;
  ans.ok = 1;
  ans.T = {yp, xp};
  return ans;
}

void testcase(){
  ll H, W; cin >> H >> W;
  V<string> A(H); REP(y,H) cin >> A[y];
  bool done = 0;
  ll rev = 0;
  ll cy = 0;
  Ans ans;

  REP(sw,2){
    REP(tt,4){
      auto ansbuf = solve(H, W, A);
      if(ansbuf.ok){ done = 1; ans = ansbuf; cy = tt; rev = sw; }
      V<string> buf(W, string(H, '.'));
      REP(y,H) REP(x,W) buf[W-1-x][y] = A[y][x];
      ans.S = {W-1-ans.S.second, ans.S.first};
      ans.T = {W-1-ans.T.second, ans.T.first};
      swap(H, W);
      swap(A, buf);
    }
    reverse(A.begin(), A.end());
  }

  if(!done){ cout << "-1\n"; return; }
  if(rev){
    reverse(ans.command.begin(), ans.command.end());
    ans.command = "F" + ans.command.substr(0, ans.command.size() - 1);
    ans.S.first = H - 1 - ans.S.first;
    ans.T.first = H - 1 - ans.T.first;
    swap(ans.S, ans.T);
    if(cy % 2 == 1) cy = (cy + 2) % 4;
  }
  cout << (ans.S.first + 1) << " " << (ans.S.second + 1) << " " << (char)("URDL"[cy]) << "\n";
  cout << ans.command.size() << "\n";
  cout << ans.command << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}
0