Untitled

mail@pastecode.io avatar
unknown
python
a year ago
2.3 kB
1
Indexable
Never
h, w = map(int, input().split())
m = []
result = []

wall = '#'


def get(p, dx, dy):
    if dx == 0 and dy == 0:
        return 1
    if dx == -1:
        if p[0] > 0:
            if dy > 0:
                if m[p[0] + dx][p[1] + dy] != wall:
                    return m[p[0] + dx][p[1] + dy]
            elif dy < 0:
                if m[p[0] + dx][p[1] + dy] != wall:
                    return m[p[0] + dx][p[1] + dy]
            else:
                if m[p[0] + dx][p[1] + dy] != wall:
                    return m[p[0] + dx][p[1] + dy]
        return 0
    if dx == 1:
        if p[0] < w - 1:
            if dy > 0:
                if m[p[0] + dx][p[1] + dy] != wall:
                    return m[p[0] + dx][p[1] + dy]
            elif dy < 0:
                if m[p[0] + dx][p[1] + dy] != wall:
                    return m[p[0] + dx][p[1] + dy]
            else:
                if m[p[0] + dx][p[1] + dy] != wall:
                    return m[p[0] + dx][p[1] + dy]
        return 0
    if dy > 0:
        if m[p[0] + dx][p[1] + dy] != wall:
            return m[p[0] + dx][p[1] + dy]
    elif dy < 0:
        if m[p[0] + dx][p[1] + dy] != wall:
            return m[p[0] + dx][p[1] + dy]
    return 0


def form(c):
    if c == wall:
        return -9999
    if c == '.':
        return 9999
    if c == 'S':
        return 0
    return 404


s = (-1, -1)
for i in range(h):
    inp = input()
    result.append(list(inp))
    m.append(list(map(form, inp)))
    if (s[0] == -1) and ('S' in inp):
        s = [len(m) - 1, inp.index('S')]

stack = [s]

while len(stack) > 0:
    pos = stack.pop(-1)
    dist = m[pos[0]][pos[1]]

    if get(pos, -1, 0) > dist + 1:
        m[pos[0] - 1][pos[1]] = dist + 1
        result[pos[0] - 1][pos[1]] = 'D'
        stack.append((pos[0] - 1, pos[1]))
    if get(pos, 1, 0) > dist + 1:
        m[pos[0] + 1][pos[1]] = dist + 1
        result[pos[0] + 1][pos[1]] = 'U'
        stack.append((pos[0] + 1, pos[1]))
    if get(pos, 0, -1) > dist + 1:
        m[pos[0]][pos[1] - 1] = dist + 1
        result[pos[0]][pos[1] - 1] = 'R'
        stack.append((pos[0], pos[1] - 1))
    if get(pos, 0, +1) > dist + 1:
        m[pos[0]][pos[1] + 1] = dist + 1
        result[pos[0]][pos[1] + 1] = 'L'
        stack.append((pos[0], pos[1] + 1))

for line in result:
    print(''.join(line))