有一个迷宫，迷宫中每个格子用
或
表示，
表示该格子可以通过，
表示该格子是个障碍物，牛妹站在格子
，出口在格子
，牛妹想要走出迷宫，但牛妹只会按以下策略走：
牛妹当前所在的格子称为当前格子
1. 如果当前格子右边没有障碍物，牛妹就向右走，否则转到2。
2. 如果当前格子下方没有障碍物，牛妹就向下走，否则转到3。
5. 牛妹站在原地不动。
由于牛妹按这样的策略可能会无法走到出口，牛妹的好朋友牛牛决定在牛妹离开格子前把迷宫中的一些非障碍格子变成障碍，帮助牛妹走出迷宫，但是牛牛比较懒，他想要最小化变成障碍的非障碍格子的数量。
第一行两个整数,
表示迷宫的大小
接下来串表示迷宫的格局
输出一个整数表示牛牛最少需要转换成障碍格子的非障碍格子的数量，如果无法帮助牛妹走出迷宫，输出。
4 4 0000 0110 0110 0000
0
这道题你会答吗？花几分钟告诉大家答案吧！
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
