时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
有一个迷宫，迷宫中每个格子用
或
表示，
表示该格子可以通过，
表示该格子是个障碍物，牛妹站在格子
，出口在格子
，牛妹想要走出迷宫，但牛妹只会按以下策略走：
牛妹当前所在的格子称为当前格子
1. 如果当前格子右边没有障碍物，牛妹就向右走，否则转到2。
2. 如果当前格子下方没有障碍物，牛妹就向下走，否则转到3。
3. 如果当前格子左边没有障碍物，牛妹就向左走，否则转到4。
4. 如果当前格子上方没有障碍物，牛妹就向上走，否则转到5。
5. 牛妹站在原地不动。
由于牛妹按这样的策略可能会无法走到出口，牛妹的好朋友牛牛决定在牛妹离开格子前把迷宫中的一些非障碍格子变成障碍，帮助牛妹走出迷宫，但是牛牛比较懒，他想要最小化变成障碍的非障碍格子的数量。
输入描述:
第一行两个整数,
表示迷宫的大小
接下来串表示迷宫的格局
输出描述:
输出一个整数表示牛牛最少需要转换成障碍格子的非障碍格子的数量，如果无法帮助牛妹走出迷宫，输出。