Путь Робота (Codeforces 648C)
Tags: Others, dfs and similar

Вам задано прямоугольное клетчатое поле, состоящее из n строк и m столбцов. Поле содержит цикл из символов «*», такой что:  цикл можно обойти, посетив каждую его клетку ровно один раз, перемещаясь каждый раз вверх/вниз/вправо/влево на одну клетку;  цикл не содержит самопересечений и самокасаний, то есть две клетки цикла соседствуют по стороне тогда и только тогда, когда они соседние при перемещении вдоль цикла (самокасание по углу тоже запрещено). Ниже изображены несколько примеров допустимых циклов:  Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:  «U» — сдвинуться на клетку вверх,  «R» — сдвинуться на клетку вправо,  «D» — сдвинуться на клетку вниз,  «L» — сдвинуться на клетку влево. Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).Найдите искомую последовательность команд, допускается любое направление обхода цикла.

Input: В первой строке входных данных записаны два целых числа n и m (3 ≤ n, m ≤ 100) — количество строк и столбцов прямоугольного клетчатого поля соответственно.В следующих n строках записаны по m символов, каждый из которых — «.», «*» или «S». Гарантируется, что отличные от «.» символы образуют цикл без самопересечений и самокасаний. Также гарантируется, что на поле ровно одна клетка содержит «S» и что она принадлежит циклу. Робот не может посещать клетки, помеченные символом «.».

Output: В первую строку выходных данных выведите искомую последовательность команд для Робота. Направление обхода цикла Роботом может быть любым.

Note: В первом тестовом примере для обхода по часовой стрелке последовательность посещенных роботом клеток выглядит следующим образом:  клетка (3, 2);  клетка (3, 1);  клетка (2, 1);  клетка (1, 1);  клетка (1, 2);  клетка (1, 3);  клетка (2, 3);  клетка (3, 3);  клетка (3, 2). 

Sample Inputs:
3 3
***
*.*
*S*

6 7
.***...
.*.*...
.*.S**.
.*...**
.*....*
.******

Sample Outputs:
LUURRDDL

UULLDDDDDRRRRRUULULL

Solution (Python):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dir = ['U', 'D', 'L', 'R']

def solve():
    (n, m) = map(int, input().split())
    a = [list(input()) for _ in range(n)]
    (sx, sy) = (-1, -1)
    for i in range(n):
        for j in range(m):
            if a[i][j] == 'S':
                (sx, sy) = (i, j)
                a[i][j] = '*'
    (px, py) = (-1, -1)
    while True:
        was_move = False
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if nx < 0 or nx >= n or ny < 0 or (ny >= m):
                continue
            if a[nx][ny] != '*':
                continue
            if nx == px and ny == py:
                continue
            a[nx][ny] = '.'
            (px, py) = (sx, sy)
            (sx, sy) = (nx, ny)
            print(dir[i], end='')
            was_move = True
            break
        if not was_move:
            break
    print()
solve()

Solution (Python):
(n, m) = map(int, input().split())
a = [list(input()) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
dirs = ['U', 'D', 'L', 'R']
(x, y) = (-1, -1)
for i in range(n):
    for j in range(m):
        if a[i][j] == 'S':
            (x, y) = (i, j)
a[x][y] = '*'
(px, py, ans) = (-1, -1, '')
while True:
    peredvinutye = False
    for i in range(4):
        (nx, ny) = (x + dx[i], y + dy[i])
        if not (0 <= nx < n and 0 <= ny < m):
            continue
        if a[nx][ny] != '*':
            continue
        if nx == px and ny == py:
            continue
        (a[nx][ny], px, py, x, y, ans, peredvinutye) = ('.', x, y, nx, ny, ans + dirs[i], True)
        break
    if not peredvinutye:
        break
print(ans)

Solution (Python):
(n, m) = map(int, input().split())
l = []
(a, b) = (-1, -1)
ss = []
for x in range(n):
    c = list(input())
    for y in range(m):
        if c[y] == 'S':
            a = x
            b = y
    l.append(c)
while True:
    k = 1
    for f in [(1, 0, 'D'), (-1, 0, 'U'), (0, 1, 'R'), (0, -1, 'L')]:
        (x1, y1) = (f[0] + a, f[1] + b)
        if 0 <= x1 < n and 0 <= y1 < m and (l[x1][y1] == '*'):
            print(f[2], end='')
            l[x1][y1] = '.'
            a = x1
            b = y1
            k = 0
            break
    if k:
        break
for f in [(1, 0, 'D'), (-1, 0, 'U'), (0, 1, 'R'), (0, -1, 'L')]:
    (x1, y1) = (f[0] + a, f[1] + b)
    if 0 <= x1 < n and 0 <= y1 < m and (l[x1][y1] == 'S'):
        print(f[2], end='')
        break