Нил научился рисовать лабиринты в прямоугольнике.
Для сохранения лабиринтов Нил придумал способ кодирования. Метод кодирования он объяснил на примере
лабиринта в прямогуольнике с 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 не рассматриваются)
то есть всего 34 ребра
Поскольку Нил не очень умеет программировать, то он просит помочь ему реализовать эту процедуру
Напишите программу, которая получает список строк одинаковой длины и возвращает число ребер
Примеры
| Входные данные |
Ответ |
Комментарий |
4
31132
22102
31102
11110
|
11
|
| Ребра |
| (0,0)-(1,0) |
(1,1)-(2,1) |
(2,2)-(2,1) |
| (1,0)-(2,0) |
(2,1)-(3,1) |
(2,1)-(2,0) |
| (1,0)-(1,1) |
(3,1)-(3,2) |
(4,0)-(4,1) |
| (0,0)-(0,1) |
(3,2)-(2,2) |
|
|
3
313332
220002
111110
|
9
|
| Ребра |
| (0,1)-(0,0) |
(1,1)-(2,1) |
(3,1)-(3,0) |
| (0,0)-(1,0) |
(2,1)-(2,0) |
(3,1)-(4,1) |
| (1,0)-(1,1) |
(2,1)-(3,1) |
(4,1),(4,0) |
|