空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Sjkmost devotes himself in spreading language virus to the whole SUSTech. Yesterday he found a secret road with length and width
between the
and the
dormitory (You can refer it as grids), so he decided to invade the
dormitory through it.
At the beginning of the semester, each grid of the road was covered by a brick. However Sjkmost's farsighted teammate FluffyBunny precisely predicted his invasion and removed some of the bricks. Initially Sjkmost is on the side of the dormitory and would like to move to the other side of the
dormitory. To secretly complete his invasion, Sjkmost can only step on bricks and move to one of the four adjacent bricks (up, down, left, right). He can choose to step on any brick at the
dormitory's side and enter the
dormitory from any brick at the
dormitory's side.
Sjkmost would be thankful if you tell him the minimum number of bricks he must add to complete his invasion, as he wants to save money for his pork elbows.
输入描述:
The first line contains two integers.
The nextlines each contain a 01-string with length
. 1 represents a brick, and 0 represents an empty unit.
Note that the first line connects with thedormitory and the last line connects with the
dormitory.
输出描述:
Output a single integer indicating the minimum number of bricks Sjkmost needs to add.
