eolymp
Competitions

Хвиля

Выход из лабиринта

Во время торнадо в Костромской области было повалено большое количество деревьев. Однажды утром, спустя пару дней после торнадо, мальчик Илья вышел прогуляться и увидел, что поваленные деревья образовывали настоящий лабиринт. Илья очень обрадовался, стал гулять и играть в лабиринте. Внезапно ему позвонил преподаватель и поинтересовался, почему он давно не видел Илью. Чтобы не получить дырку в бейджик за самовольный выход за территорию лагеря, Илья, конечно же, хотел попасть в домик как можно скорее, но и побродить по лабиринту ему тоже хотелось.

Помогите ему узнать, как быстро он сможет добраться до домика.

Входные данные

В первой строке входного файла заданы целые положительные числа N и M (1N, M1000). В следующих N строках заданы по M символов, описывающих лабиринт. На позициях, по которым Илья может перемещаться, записан символ "0", а на позициях, которые перегорожены деревьями, записан символ "1". После описания лабиринта следуют целые числа x1, y1, x2, y2 - координаты (то есть соответствующие номера столбцов и строк) Ильи и его домика (1x1, x2M, 1y1, y2N).

Выходные данные

В выходной файл выведите единственное число - длину кратчайшего пути от точки (x1, y1) до точки (x2, y2), если Илья может добраться до дому по лабиринту, и "-1" в противном случае.

Time limit 1 second
Memory limit 64 MiB
Input example #1
4 6
1 0 1 1 1 0
0 0 1 0 0 0
1 0 1 1 0 0
0 0 0 0 0 0
2 1
5 3
Output example #1
7