971. Роботы

Вы когда-нибудь видели роботов? Ну хотя бы одного? Нет? А вот мне довелось однажды… И не одного, а целых двух. Тогда я как раз умудрился попасть на транзисторный завод где-то под Хабаровском. Или Харбином… Теперь уже без разницы, но всё же. Так или иначе, я наблюдал за роботами. Два странных электромеханических парня неуклюже передвигались по территории склада, пытаясь за минимальное время достичь заданных оператором точек. Печальное зрелище… Сталкивающиеся лбами железяки и пунцовый оператор, пытающийся как-то разрешить ситуацию. Я тогда было подумал, что, быть может, есть возможность как-то улучшить… усовершенствовать этот процесс. Но застарелый интернетоголизм не дал раскрыться моему таланту. С завода меня вскоре уволили, и вот с тех пор я несколько охладел к работе… Но не к задаче! До сих пор, сидя в четыре утра на подоконнике в подъезде, я пытаюсь придумать, как же провести этих роботов сквозь все закоулки. Как бы это так завернуть…

В первой строке – `N` (размер поля, `2\ ≤\ N\ ≤\ 30`). В следующих `N` строках – по `N` символов в каждой ('.' – пусто, 'x' – стена). Далее идут 2 строки, описывающие роботов в формате: `X_1,\ Y_1,\ X_2,\ Y_2` (`1\ ≤\ X_1,\ Y_1,\ X_2,\ Y_2\ ≤\ N`), где `X_1,\ Y_1` – номер столбца и строки, в которых находится робот в начале, `X_2,\ Y_2` – соответственно, куда он должен прийти. Начальные позиции роботов не совпадают.

Минимальное количество шагов, за которое роботы могут прийти из своих начальных точек в конечные. На каждом шаге двигаться могут оба робота, но каждый из роботов может пойти только в незанятую другим роботом или стеной ячейку (в момент начала движения). Так же, два робота не могут пойти в одну и ту же ячейку одновременно. Естественно, на каждом шаге роботы могут ходить только в четыре соседние с ними ячейки: `(X-1,Y)`, `(X+1,Y)`, `(X,Y-1)`, `(X,Y+1)`. Так же роботы не могут выйти за края поля. Если роботы никогда не смогут занять свои конечные позиции, то вывести число `-1`.

9
.........
.........
xxx...xxx
..xxxxx..
.........
..xxxxx..
xxx...xxx
.........
.........
1 6 9 4
9 4 1 6

18