Нил научился рисовать лабиринты в прямоугольнике.
Для сохранения лабиринтов Нил придумал способ кодирования. Метод кодирования он объяснил на примере
лабиринта в прямогуольнике с 5 строками и 7 столбцами
Для каждой клетки таблицы (включая строку 5 и столбец h) рассматривается
"левый нижний угол". Из этого угла могут исходить линии "вверх"(U) и "вправо" (R)
Всего может быть четыре варианта:
- UR (RU) - кодидуем числом 3 (двоичное представление 11)
- U - кодидуем числом 2 (двоичное представление 10)
- R - кодидуем числом 3 (двоичное представление 01)
- нет исходящих линий - кодируем числом 0 (двоичное представление 00)
| Кодировки клеток |
| 5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
| 4 |
2 |
0 |
2 |
2 |
2 |
0 |
2 |
2 |
| 3 |
2 |
2 |
0 |
1 |
2 |
2 |
1 |
2 |
| 2 |
2 |
2 |
2 |
2 |
1 |
3 |
0 |
2 |
| 1 |
3 |
2 |
3 |
0 |
1 |
2 |
0 |
2 |
| 0 |
3 |
1 |
3 |
1 |
3 |
1 |
3 |
2 |
| |
a |
b |
c |
d |
e |
f |
g |
h |
Нил решил, кодировку он запишет ввиде 6 строк по 8 символов в каждой. Для примера, набор строк будет выглядеть:
'31313132', '32301202', '22221302', '22012212', '20222022', '11111110'
Нил захотел исследовать свой лабиринт, чтобы использовать его для различных целей (игры с фишками, поле для роботов и т.п.),
но для этого ему нужно построить "граф лабиринта" - то есть определить все возможные переходы (ребра)
Для примера это будет выгледеть так
a0 - b0; b0-b1; c0 - d0; d0 - d1; e0 - f1; f0 - f1; g0 - g1;
a1 - a2; b1 - b2; c1 - c2; c1 -d1; d1 - d2; d1 - e1; f1 - g1; g1 - g2;
a2 - a3; b2 - b3;c2 - c3; d2 - e2; e2 - e3; f2 - f3; f2 - g2;
a3 - a4; b3 - b4; b3 - c3; c3 - c4; c3 - d3; d3 - d4; e3 - e4; f3 - f4; f3 - g3; g3 - g4;
a4 - b4; e4 - f4;
(вершины вида h& и ?5 не рассматриваются)
Поскольку Нил не очень умеет программировать, то он просит помочь ему реализовать эту процедуру
Напишите подпрограмму, которая получает список строк одинаковой длины и возвращает список ребер
"табличного лабиринта", где каждое ребро есть кортеж пар координат "соседних" ячеек таблицы (нумерация строк и столбцов с нуля)
Пример
| Входные данные |
Ожидаемый результат |
['31132', '22102', '31102', '11110']
|
[((0,0),(1,0)),(1,0),(1,0)),(1,0),(1,1)),(4,0),(4,1)),(1,1),(2,1)),(2,1),(3,1)),(3,1),(3,2)),
(3,2),(2,2)),(2,2),(2,1)),(2,1),(2,0))] |
['313332', '220002', '111110']
|
[((0,1),(0,0)),((0,0),(1,0)),((1,0),(1,1)),((1,1),(2,1)),((2,1),(2,0)),((2,1),(3,1)),((3,1),(3,0)),
((3,1),(4,1)),((4,1),(4,0))) |