3AUnreviewed1000GPT-5.4 (high)

Shortest path of the king

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

greedy shortest paths

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Map each square to coordinates $(x,y)$ . What can one king move change about $x$ and $y$ ?

Unlike a rook, the king can fix horizontal and vertical difference in the same move. So think in terms of $dx$ and $dy$ , not Manhattan distance.

If $dx = |x_1-x_2|$ and $dy = |y_1-y_2|$ , one move can reduce each by at most $1$ . Therefore you need at least $\max(dx,dy)$ moves.

That lower bound is achievable: while both coordinates still differ, move diagonally toward the target, which reduces both differences by $1$ . Once one coordinate matches, keep moving straight in the other direction.

Simulate it directly. On each step, start with an empty string move; append R/L depending on the file and U/D depending on the rank. This automatically gives one of L, R, U, D, LU, LD, RU, RD, and the number of steps is exactly $\max(dx,dy)$ .

Observation 1

This is barely a shortest-path problem. Yes, you could BFS over $64$ squares, but that's like bringing a tank to a pillow fight.

Let the start be $(x_1,y_1)$ and the target be $(x_2,y_2)$ , where the letter is the $x$ -coordinate and the digit is the $y$ -coordinate.

In one king move, both coordinates can change by at most $1$ : $|\Delta x| \le 1, \qquad |\Delta y| \le 1.$

So if $dx = |x_2-x_1|, \qquad dy = |y_2-y_1|,$ then any path needs at least $\max(dx,dy)$ moves, because a single move cannot reduce either difference by more than $1$ .

Observation 2

That lower bound is also achievable.

While both $dx>0$ and $dy>0$ , move diagonally toward the target.
After one coordinate matches, move straight along the remaining coordinate.

So the minimum number of moves is exactly $\max(dx,dy).$

In metric-speak, $d_\infty((x_1,y_1),(x_2,y_2)) = \max(|x_2-x_1|, |y_2-y_1|).$ Fancy name, tiny implementation.

Greedy construction

Maintain the current square $(x,y)$ .

At each step:

if $x < x_2$ , append R and do $x \leftarrow x+1$
if $x > x_2$ , append L and do $x \leftarrow x-1$
if $y < y_2$ , append U and do $y \leftarrow y+1$
if $y > y_2$ , append D and do $y \leftarrow y-1$

The move string you build is automatically one of: L, R, U, D, LU, LD, RU, RD.

Why does this work? Because every iteration decreases each nonzero coordinate difference by exactly $1$ . Therefore the value $D = \max(|x-x_2|, |y-y_2|)$ drops by exactly $1$ each time, until it becomes $0$ .

So after exactly the optimal number of steps, you're done. Clean, greedy, no nonsense.

Complexity

Let $D = \max(|x_2-x_1|, |y_2-y_1|).$

The simulation runs for exactly $D$ moves, so the complexity is $O(D) = O(\max(dx,dy)),$ which is at most $7$ on an $8 \times 8$ board. Memory usage is $O(1)$ besides the output itself.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    string s, t;
    cin >> s >> t;

    int x = s[0] - 'a';
    int y = s[1] - '1';
    int tx = t[0] - 'a';
    int ty = t[1] - '1';

    vector<string> ans;

    while (x != tx || y != ty) {
        string mv;

        if (x < tx) {
            mv += 'R';
            ++x;
        } else if (x > tx) {
            mv += 'L';
            --x;
        }

        if (y < ty) {
            mv += 'U';
            ++y;
        } else if (y > ty) {
            mv += 'D';
            --y;
        }

        ans.push_back(mv);
    }

    cout << ans.size() << '\n';
    for (const string& mv : ans) {
        cout << mv << '\n';
    }
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    string s, t;
    cin >> s >> t;

    int x = s[0] - 'a';
    int y = s[1] - '1';
    int tx = t[0] - 'a';
    int ty = t[1] - '1';

    vector<string> ans;

    while (x != tx || y != ty) {
        string mv;

        if (x < tx) {
            mv += 'R';
            ++x;
        } else if (x > tx) {
            mv += 'L';
            --x;
        }

        if (y < ty) {
            mv += 'U';
            ++y;
        } else if (y > ty) {
            mv += 'D';
            --y;
        }

        ans.push_back(mv);
    }

    cout << ans.size() << '\n';
    for (const string& mv : ans) {
        cout << mv << '\n';
    }
}

View on Codeforces Back to the list