[CodeQUEEN 2024 予選 (ABC 358)]F - Easiest Maze
[Q] F - Easiest Maze
間に合いませんでした。40分くらい残して初全完がかかっていたのですが残念。
難しいけど、マイルール決めてお絵描きすればいいので、時間をかけて丁寧にやれば絶対できる問題だったなと思う。
考察
1. Noは2パターン
a. 最小マスは直下でNマス。K < Nの場合No
b. 最大を考える。ルートを変えることで消費マスが2増えるので、N + 2n消費できる。(K - N) % 2 == 1の場合No。
それ以外はYesなので、だいたいYes
2. N >= 2なので、1 3 3とかは考えなくていい。ありがたい。
1 3 3 は考えなくていい。
Yes
+++++S+
+o|o|o+
+++++G+3. Nの偶奇で動きを分けられる。 N=偶数の場合が簡単。
左下右下にうねりながら移動すれば、Gにぴったり到達できる。
4 3 10
Yes
+++++S+
+o.o.o+
+.+-+-+
+o.o.o+
+-+-+.+
+o|o.o+
+-+.+-+
+o|o.o+
+++++G+4. N=奇数の場合を考える。
a. 最後の4行になるまで左下右下…左下、で左右に蛇行移動する。
b. 最後の4行は下右上右…下、で上下に蛇行移動する。
3 4 11
Yes
+++++++S+
+o.o.o.o+
+.+-+-+-+
+o|o.o.o+
+.+.+-+.+
+o.o|o|o+
+++++++G+
5, 作りたい形を思い描けたので、実装方法を考える。
a. 'o' を移動可能マスと考える。
自分のスタート地点を(1, M * 2 - 1)としてGまで移動する。
move(&y, &x, dir)を作ると管理しやすい。
b. 通過したマスを + -> . にしてGまでたどり着く
c. 偶数行をみて、 + -> | にする
d. 奇数行をみて、 + -> - にする
3 4 11
+++++++S+ +++++++S+ +++++++S+
+o+o+o+o+ +o.o.o.o+ +o.o.o.o+
+++++++++ +.+++++++ +.+-+-+-+
+o+o+o+o+ -> +o+o.o.o+ -> +o|o.o.o+
+++++++++ +.+.+++.+ +.+.+-+.+
+o+o+o+o+ +o.o+o+o+ +o.o|o|o+
+++++++G+ +++++++G+ +++++++G+
実装
int main()
{
int N, M, K;
cin >> N >> M >> K;
// Noのパターン
if (K < N || (K - N) % 2)
{
cout << "No" << endl;
return 0;
}
cout << "Yes" << endl;
vector<string> maze(2 * N + 1, string(2 * M + 1, '+'));
rep(i, N) rep(j, M)
{
maze[1 + i * 2][1 + j * 2] = 'o';
}
auto move = [&](ll &y, ll &x, char d)
{
ll dir = "URDL"s.find(d);
maze[y + dy[dir]][x + dx[dir]] = '.';
y += dy[dir] * 2;
x += dx[dir] * 2;
};
ll y = 1, x = M * 2 - 1;
// こぶをいくつ減らすか。
vector<ll> detour(N / 2, 0);
ll k = K - N;
k /= 2; // こぶのかず
rep(n, N / 2)
{
ll sub = min(M - 1LL, k);
detour[n] = sub;
k -= sub;
if (k == 0)
break;
}
if (N % 2 == 0) // 偶数なら左下右下
{
rep(det, N / 2)
{
rep(i, detour[det])
{
move(y, x, 'L');
}
move(y, x, 'D');
rep(i, detour[det])
{
move(y, x, 'R');
}
move(y, x, 'D');
}
}
else
{
rep(det, N / 2)
{
rep(i, detour[det])
{
move(y, x, 'L');
}
move(y, x, 'D');
if (det == N / 2 - 1) // 奇数なら、最後の2行だけ上下移動
break;
rep(i, detour[det])
{
move(y, x, 'R');
}
move(y, x, 'D');
}
while(x < M * 2 - 1)
{
if (k > 0)
{
move(y, x, 'D');
move(y, x, 'R');
move(y, x, 'U');
--k;
}
move(y, x, 'R');
}
move(y, x, 'D');
}
// + -> |
rep(i, N){
rep(j, M - 1){
if (maze[i * 2 + 1][j * 2 + 2] == '+')
maze[i * 2 + 1][j * 2 + 2] = '|';
}
}
// + -> -
rep(i, N - 1){
rep(j, M){
if (maze[i * 2 + 2][j * 2 + 1] == '+')
maze[i * 2 + 2][j * 2 + 1] = '-';
}
}
maze[0][M * 2 - 1] = 'S';
maze[N * 2][M * 2 - 1] = 'G';
for (auto s : maze)
{
cout << s << endl;
}
}