Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.3 kB
2
Indexable
Never
h, w = map(int, input().split())
m = []
result = []

wall = '#'


def get(p, dx, dy):
    if m[p[0] + dx][p[1] + dy] != wall:
        return m[p[0] + dx][p[1] + dy]
    return -99999


def form(c):
    if c == wall:
        return -999999
    if c == '.':
        return 999999
    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))