| Codeforces Round 402 (Div. 1) |
|---|
| Закончено |
Петя решил положить паркет в комнате размером n × m, паркет состоит из досок размером 1 × 2. Когда строители уложили паркет, выяснилось, что его рисунок выглядит совсем не так, как нравится Пете, и строителям придется его переложить.
Однако строители решили, что снимать паркет целиком и потом раскладывать его заново очень сложно, поэтому каждый час они будут делать такую операцию: вынуть какие-то две доски, образующие квадрат 2 × 2, повернуть их на 90 градусов и положить на то же место.
При этом у них нет никаких идей, как с помощью таких операций получить требуемое расположение, и возможно ли это вообще.
Помогите Пете составить план для рабочих или скажите, что это невозможно. План должен содержать не более 100 000 команд.
Первая строка входных данных содержит числа n и m — размер комнаты (1 ≤ n, m ≤ 50). Хотя бы одно из двух заданных чисел — четно.
Следующие n строк содержат по m символов — описание текущего положения досок паркета. Каждый символ обозначает положение половинки доски. Символы 'L', 'R', 'U' и 'D' соответствуют левой, правой, верхней и нижней половинкам соответственно.
Следующие n строк содержат по m символов содержат описание требуемой конфигурации в том же формате.
В первой строке выведите k — число операций в плане для рабочих. В следующих k строках выведите описания операций. Операция задается координатами (строка и столбец) левой верхней половинки доски, над которыми проводится операция.
Если решения нет, выведите в первой строке -1.
2 3
ULR
DLR
LRU
LRD
2
1 2
1 1
4 3
ULR
DLR
LRU
LRD
ULR
DUU
UDD
DLR
3
3 1
3 2
2 2
В первом примере первой операцией поворачиваем две правые доски, после чего все доски лежат вертикально. После этого второй операцией поворачиваем две левые доски, получаем требуемую конфигурацию.
