Submission #65212860

---

Source Code Expand

import sys

def signum(x):
    return (x > 0) - (x < 0)

def get_distance(p1, p2)->int:
    return abs(p1[0]-p2[0])+abs(p1[1]-p2[1])

def generate_steps(p1, p2):
    steps=[]
    vertical_steps = p2[0]-p1[0]
    horizontal_steps = p2[1]-p1[1]
    if vertical_steps != 0:
        steps += ([f"M {'D' if signum(vertical_steps) > 0 else 'U'}"] * abs(vertical_steps))
    if horizontal_steps != 0:
        steps += ([f"M {'R' if signum(horizontal_steps) > 0 else 'L'}"] * abs(horizontal_steps))

    return steps

def slide_to(p1, p2):
    steps = []
    signs = (signum(p2[0] - p1[0]), signum(p2[1] - p1[1]))
    if p1[0] != p2[0]:
        steps.append(f"S {'D' if signs[0] > 0 else 'U'}")
    if p1[1] != p2[1]:
        steps.append(f"S {'R' if signs[1] > 0 else 'L'}")
    return steps

def get_best_var(var1, var2):
    return var1 if len(var1) < len(var2) else var2

def get_best_trivial(from_pos, to_pos, N):
    best_var = []
    commands = []
    commands += generate_steps(from_pos, to_pos)
    best_var = commands

    commands = []
    commands += slide_to(from_pos, (0, 0))
    commands += generate_steps((0, 0), to_pos)
    best_var = get_best_var(best_var, commands)

    commands = []
    commands += slide_to(from_pos, (0, N - 1))
    commands += generate_steps((0, N - 1), to_pos)
    best_var = get_best_var(best_var, commands)

    commands = []
    commands += slide_to(from_pos, (N - 1, N - 1))
    commands += generate_steps((N - 1, N - 1), to_pos)
    best_var = get_best_var(best_var, commands)

    commands = []
    commands += slide_to(from_pos, (N - 1, 0))
    commands += generate_steps((N - 1, 0), to_pos)
    best_var = get_best_var(best_var, commands)

    commands = []
    commands += slide_to(from_pos, (from_pos[0], 0))
    commands += generate_steps((from_pos[0], 0), to_pos)
    best_var = get_best_var(best_var, commands)

    commands = []
    commands += slide_to(from_pos, (from_pos[0], N - 1))
    commands += generate_steps((from_pos[0], N - 1), to_pos)
    best_var = get_best_var(best_var, commands)

    commands = []
    commands += slide_to(from_pos, (N - 1, from_pos[1]))
    commands += generate_steps((N - 1, from_pos[1]), to_pos)
    best_var = get_best_var(best_var, commands)

    commands = []
    commands += slide_to(from_pos, (N - 1, from_pos[1]))
    commands += generate_steps((N - 1, from_pos[1]), to_pos)
    best_var = get_best_var(best_var, commands)

    if to_pos[0] in {0, N-1}:
        commands = []
        commands += generate_steps(from_pos, (from_pos[0], to_pos[1]))
        commands += slide_to((from_pos[0], to_pos[1]), to_pos)
        best_var = get_best_var(best_var, commands)

    if to_pos[1] in {0, N - 1}:
        commands = []
        commands += generate_steps(from_pos, (to_pos[0], from_pos[1]))
        commands += slide_to((to_pos[0], from_pos[1]), to_pos)
        best_var = get_best_var(best_var, commands)

    return best_var

def check_point(point, dst_point, N):
    max_r = 10
    best_var = get_best_trivial(point, dst_point, N)
    if len(best_var) <= 2:
        return best_var
    for radius in range(1, max_r+1):
        l, t = point[1]-radius, point[0]-radius
        r, b = point[1]+radius, point[0]+radius
        for line in range(t,b+1):
            if N > line >= 0:
                for col in range(l,r+1):
                    if N > col >= 0:
                        commands =[]
                        commands += generate_steps(point, (line, col))
                        commands += get_best_trivial((line, col), dst_point, N)
                        if len(commands) < len(best_var):
                            best_var = commands
    return best_var

def main():
    input = sys.stdin.readline
    N, M = [int(e) for e in input().split()]
    field = [[0 for _ in range(N)] for _ in range(N)]

    cur_pos = [int(e) for e in input().split()]
    points = []
    for _ in range(1,M):
        x,y = [int(e) for e in input().split()]
        points.append((x,y))

    total_commands_len = 0

    for point in points:
        commands = check_point(cur_pos, point, N)
        total_commands_len += len(commands)
        if total_commands_len > 2*N*M:
            break
        for command in commands:
            print(command)
        print()
        cur_pos = point

main()

Submission Info

Judge Result