# Untitled

unknown
python
2 years ago
2.3 kB
3
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))```