codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

648C.md (4680B)


      1 Source: https://codeforces.com/problemset/problem/648/C
      2 
      3 C. Путь Робота
      4 
      5 ограничение по времени на тест
      6 
      7 2 секунды
      8 
      9 ограничение по памяти на тест
     10 
     11 256 мегабайт
     12 
     13 ввод
     14 
     15 стандартный ввод
     16 
     17 вывод
     18 
     19 стандартный вывод
     20 
     21 Вам задано прямоугольное клетчатое поле, состоящее из *n* строк и *m* столбцов. Поле содержит цикл из символов «*», такой что:
     22 
     23 * цикл можно обойти, посетив каждую его клетку ровно один раз, перемещаясь каждый раз вверх/вниз/вправо/влево на одну клетку;
     24 * цикл не содержит самопересечений и самокасаний, то есть две клетки цикла соседствуют по стороне тогда и только тогда, когда они соседние при перемещении вдоль цикла (самокасание по углу тоже запрещено).
     25 
     26 Ниже изображены несколько примеров допустимых циклов:
     27 
     28  ![](https://espresso.codeforces.com/b44934f2744e9a343989bf7e08f3978c491ba485.png) 
     29 
     30 Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.
     31 
     32 В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:
     33 
     34 * «U» — сдвинуться на клетку вверх,
     35 * «R» — сдвинуться на клетку вправо,
     36 * «D» — сдвинуться на клетку вниз,
     37 * «L» — сдвинуться на клетку влево.
     38 
     39 Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).
     40 
     41 Найдите искомую последовательность команд, допускается любое направление обхода цикла.
     42 
     43 Входные данные
     44 
     45 В первой строке входных данных записаны два целых числа *n* и *m* (3 ≤ *n*, *m* ≤ 100) — количество строк и столбцов прямоугольного клетчатого поля соответственно.
     46 
     47 В следующих *n* строках записаны по *m* символов, каждый из которых — «.», «*» или «S». Гарантируется, что отличные от «.» символы образуют цикл без самопересечений и самокасаний. Также гарантируется, что на поле ровно одна клетка содержит «S» и что она принадлежит циклу. Робот не может посещать клетки, помеченные символом «.».
     48 
     49 Выходные данные
     50 
     51 В первую строку выходных данных выведите искомую последовательность команд для Робота. Направление обхода цикла Роботом может быть любым.
     52 
     53 Примеры
     54 
     55 Входные данные
     56 
     57 ```
     58 3 3  
     59 ***  
     60 *.*  
     61 *S*
     62 ```
     63 
     64 Выходные данные
     65 
     66 ```
     67 LUURRDDL
     68 ```
     69 
     70 Входные данные
     71 
     72 ```
     73 6 7  
     74 .***...  
     75 .*.*...  
     76 .*.S**.  
     77 .*...**  
     78 .*....*  
     79 .******
     80 ```
     81 
     82 Выходные данные
     83 
     84 ```
     85 UULLDDDDDRRRRRUULULL
     86 ```
     87 
     88 Примечание
     89 
     90 В первом тестовом примере для обхода по часовой стрелке последовательность посещенных роботом клеток выглядит следующим образом:
     91 
     92 1. клетка (3, 2);
     93 2. клетка (3, 1);
     94 3. клетка (2, 1);
     95 4. клетка (1, 1);
     96 5. клетка (1, 2);
     97 6. клетка (1, 3);
     98 7. клетка (2, 3);
     99 8. клетка (3, 3);
    100 9. клетка (3, 2).