結果
| 問題 | No.3738 Right Hamiltonian |
| コンテスト | |
| ユーザー |
👑  kencho
|
| 提出日時 | 2026-08-18 02:49:55 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 821 ms / 2,000 ms |
| + 851µs | |
| コード長 | 8,924 bytes |
| 記録 | |
| コンパイル時間 | 3,030 ms |
| コンパイル使用メモリ | 357,916 KB |
| 実行使用メモリ | 61,756 KB |
| 最終ジャッジ日時 | 2026-09-19 12:39:02 |
| 合計ジャッジ時間 | 8,795 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点 | 80 % | AC * 38 |
| 満点 | 20 % | AC * 60 |
| 合計 | 4 * 100% = 400 点 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
struct Seg { int r, c, d, n; };
struct Rect { int u, d, l, r; };
int H, W, tot, U, D, L, R;
vector<string> a;
vector<array<unsigned short, 4>> ray;
vector<int> sum;
vector<unsigned char> used;
const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
int num(int r, int c) { return r * W + c; }
int row(int p) { return p / W; }
int col(int p) { return p % W; }
int direction(int x, int y) {
int r = row(y) - row(x), c = col(y) - col(x);
for (int d = 0; d < 4; ++d)
if (r == dr[d] && c == dc[d]) return d;
return -1;
}
vector<int> border() {
vector<int> p;
for (int c = L; c < R; ++c) p.push_back(num(U, c));
for (int r = U; r < D; ++r) p.push_back(num(r, R));
for (int c = R; c > L; --c) p.push_back(num(D, c));
for (int r = D; r > U; --r) p.push_back(num(r, L));
return p;
}
bool inside(Rect z, int r, int c) {
return z.u <= r && r <= z.d && z.l <= c && c <= z.r;
}
int count(Rect z) {
if (z.u > z.d || z.l > z.r) return 0;
auto s = [&](int r, int c) { return sum[r * (W + 1) + c]; };
return s(z.d + 1, z.r + 1) - s(z.u, z.r + 1)
- s(z.d + 1, z.l) + s(z.u, z.l);
}
// z の中を、st から turn 方向へ曲がり続けて貪欲にたどる。
bool spiral(Rect z, int st, int d, int turn, vector<Seg>& v) {
v.clear();
int r = row(st), c = col(st), got = 0;
for (int first = 1;; first = 0, d = (d + turn + 4) % 4) {
auto get = [&]() {
int x = r + dr[d], y = c + dc[d];
if (!inside(z, x, y) || a[x][y] == '#') return 0;
int n = d == 0 ? x - z.u + 1 : d == 1 ? z.r - y + 1
: d == 2 ? z.d - x + 1 : y - z.l + 1;
n = min<int>(n, ray[num(x, y)][d]);
if (v.size() >= 3) {
Seg q = v[v.size() - 3];
int qr = q.r + dr[q.d] * q.n;
int qc = q.c + dc[q.d] * q.n;
if ((d & 1) && min(q.r, qr) <= r && r <= max(q.r, qr)) {
int e = (q.c - c) * dc[d];
if (!e) return -1;
if (e > 0) n = min(n, e - 1);
}
if (!(d & 1) && min(q.c, qc) <= c && c <= max(q.c, qc)) {
int e = (q.r - r) * dr[d];
if (!e) return -1;
if (e > 0) n = min(n, e - 1);
}
}
return n;
};
int n = get();
if (first && n == 0) {
d = (d + turn + 4) % 4;
n = get();
}
if (n < 0) return false;
if (!n) break;
if (v.size() >= 2 && n >= v[v.size() - 2].n) return false;
v.push_back({r, c, d, n});
r += dr[d] * n;
c += dc[d] * n;
got += n;
}
return got == count(z);
}
// 外周が真の区間なら一度しか呼ばれないので、こちらはセル単位でよい。
void trace(int st, int d, int turn, int tag, int& cnt, vector<Seg>& v) {
int r = row(st), c = col(st);
while (true) {
int sr = r, sc = c, n = 0;
while (true) {
int x = r + dr[d], y = c + dc[d];
if (x < 0 || x >= H || y < 0 || y >= W ||
a[x][y] == '#' || used[num(x, y)] == tag) break;
r = x; c = y; ++n; ++cnt; used[num(r, c)] = tag;
}
if (n) v.push_back({sr, sc, d, n});
d = (d + turn + 4) % 4;
int x = r + dr[d], y = c + dc[d];
if (x < 0 || x >= H || y < 0 || y >= W ||
a[x][y] == '#' || used[num(x, y)] == tag) break;
}
}
void add(vector<pair<int,int>>& v, int d, int n) {
if (!n) return;
if (!v.empty() && v.back().first == d) v.back().second += n;
else v.push_back({d, n});
}
void reverse_arm(vector<pair<int,int>>& run, const vector<Seg>& v) {
for (int i = (int)v.size() - 1; i >= 0; --i) add(run, v[i].d ^ 2, v[i].n);
}
void forward_arm(vector<pair<int,int>>& run, const vector<Seg>& v) {
for (auto s : v) add(run, s.d, s.n);
}
bool output(int start, const vector<pair<int,int>>& run) {
int moves = 0;
string cmd;
for (int i = 0; i < (int)run.size(); ++i) {
int d = run[i].first, n = run[i].second;
if (i && d != (run[i - 1].first + 1) % 4) return false;
moves += n;
cmd += i ? 'R' : 'F';
cmd.append(n - 1, 'F');
}
if (moves != tot - 1) return false;
cout << row(start) + 1 << ' ' << col(start) + 1 << ' '
<< "URDL"[run.empty() ? 0 : run[0].first] << '\n';
cout << moves << '\n' << cmd << '\n';
return true;
}
bool partial(const vector<int>& arc, int order) {
int tag = order + 1, cnt = arc.size();
for (int x : arc) used[x] = tag;
vector<Seg> x, y;
int fd = direction(arc[0], arc[1]);
int ld = direction(arc[arc.size() - 2], arc.back());
if (!order) {
trace(arc[0], fd ^ 2, -1, tag, cnt, x);
trace(arc.back(), ld, 1, tag, cnt, y);
} else {
trace(arc.back(), ld, 1, tag, cnt, y);
trace(arc[0], fd ^ 2, -1, tag, cnt, x);
}
if (cnt != tot) return false;
vector<pair<int,int>> run;
reverse_arm(run, x);
for (int i = 1; i < (int)arc.size(); ++i)
add(run, direction(arc[i - 1], arc[i]), 1);
forward_arm(run, y);
int start = x.empty() ? arc[0]
: num(x.back().r + dr[x.back().d] * x.back().n,
x.back().c + dc[x.back().d] * x.back().n);
return output(start, run);
}
bool full(const vector<int>& p) {
int n = p.size(), iu = U + 1, id = D - 1, il = L + 1, ir = R - 1;
vector<Seg> x, y;
for (int k = 0; k < n; ++k) {
int A = p[(k + 1) % n], B = p[k];
int ar = row(A), ac = col(A), br = row(B), bc = col(B);
Rect xz, yz;
if (ar == br) {
int q = max(ac, bc);
Rect l{iu, id, il, q - 1}, r{iu, id, q, ir};
tie(xz, yz) = ac >= q ? pair{r, l} : pair{l, r};
} else {
int q = max(ar, br);
Rect u{iu, q - 1, il, ir}, d{q, id, il, ir};
tie(xz, yz) = ar >= q ? pair{d, u} : pair{u, d};
}
int fd = direction(A, p[(k + 2) % n]);
int ld = direction(p[(k + n - 1) % n], B);
if (!spiral(xz, A, fd ^ 2, -1, x) || !spiral(yz, B, ld, 1, y)) continue;
vector<pair<int,int>> run;
reverse_arm(run, x);
for (int i = 1; i < n; ++i)
add(run, direction(p[(k + i) % n], p[(k + i + 1) % n]), 1);
forward_arm(run, y);
int start = x.empty() ? A
: num(x.back().r + dr[x.back().d] * x.back().n,
x.back().c + dc[x.back().d] * x.back().n);
if (output(start, run)) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> H >> W;
a.resize(H);
for (auto& s : a) cin >> s;
U = H; D = -1; L = W; R = -1;
for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) if (a[r][c] == '.') {
++tot; U = min(U, r); D = max(D, r); L = min(L, c); R = max(R, c);
}
if (U == D || L == R) {
int len = U == D ? R - L + 1 : D - U + 1;
if (len != tot) return cout << -1 << '\n', 0;
vector<pair<int,int>> run;
if (len > 1) run.push_back({U == D ? 1 : 2, len - 1});
output(num(U, L), run);
return 0;
}
vector<int> p = border(), arc;
int n = p.size(), floors = 0, start = -1, blocks = 0;
for (int i = 0; i < n; ++i) floors += a[row(p[i])][col(p[i])] == '.';
if (floors < n) {
for (int i = 0; i < n; ++i)
if (a[row(p[i])][col(p[i])] == '.' &&
a[row(p[(i + n - 1) % n])][col(p[(i + n - 1) % n])] == '#')
start = i, ++blocks;
if (blocks != 1) return cout << -1 << '\n', 0;
for (int i = start; a[row(p[i])][col(p[i])] == '.'; i = (i + 1) % n)
arc.push_back(p[i]);
used.resize(H * W);
if (arc.size() >= 2 && (partial(arc, 0) || partial(arc, 1))) return 0;
return cout << -1 << '\n', 0;
}
ray.assign(H * W, {});
for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) if (a[r][c] == '.')
ray[num(r,c)][0] = 1 + (r ? ray[num(r-1,c)][0] : 0);
for (int r = 0; r < H; ++r) for (int c = W - 1; c >= 0; --c) if (a[r][c] == '.')
ray[num(r,c)][1] = 1 + (c + 1 < W ? ray[num(r,c+1)][1] : 0);
for (int r = H - 1; r >= 0; --r) for (int c = 0; c < W; ++c) if (a[r][c] == '.')
ray[num(r,c)][2] = 1 + (r + 1 < H ? ray[num(r+1,c)][2] : 0);
for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) if (a[r][c] == '.')
ray[num(r,c)][3] = 1 + (c ? ray[num(r,c-1)][3] : 0);
sum.assign((H + 1) * (W + 1), 0);
for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c)
sum[(r+1)*(W+1)+c+1] = (a[r][c] == '.') + sum[r*(W+1)+c+1]
+ sum[(r+1)*(W+1)+c] - sum[r*(W+1)+c];
if (!full(p)) cout << -1 << '\n';
}