十六夜咲夜正准备为蕾米莉亚大小姐端上红茶。红魔馆的走廊可以看作一个 行 列的网格图。由于大小姐对红茶的平稳度有极高的要求，咲夜在移动时必须遵循极其严格的规则：她只能向右或向下移动。 走廊的每个格点 可能放置了不同的物件。具体定义如下： - 若格点数值为 ，表示该处为空旷的走廊，可以通行。 - 若格点数值为 中的任意一种，分别代表家具、电源、孔洞或地线，这些均被视为障碍物，无法通行。 咲夜需要从左上角的厨房 出发，到达右下角的大小姐房间 。为了保证红茶不溢出，她希望在移动过程中尽可能减少转向的次数。所谓“转向”，是指移动方向从“向右”变为“向下”，或从“向下”变为“向右”。 请你计算在保证只经过数值为 的格点，且仅向右或向下移动的前提下，从起点到终点所需的最少转向次数。
输入描述:
输入包含一个测试用例。 第一行包含两个整数 和 ()，分别表示走廊的行数和列数。 若 和 在合法范围内，接下来将有 行输入，每行包含 个整数，代表网格中每个位置的数值 ()。 特别地，如果 或 的取值范围不在 之内，则视为无效输入。
输出描述:
输出一个整数，表示从 到 所需的最少转向次数。 如果无法到达终点，或输入维度无效，请输出 。
示例1
说明
样例中走廊为
的矩阵。其中
)
和
)
为障碍物。
从起点
)
到终点
)
存在以下两条路径：
1.
%20%5Cto%20(1%2C0)%20%5Cto%20(1%2C1)%20%5Cto%20(1%2C2)%20%5Cto%20(2%2C2))
：
- 方向变化为：下
右（第 1 次转向）
右
下（第 2 次转向）。共转向 2 次。
2.
%20%5Cto%20(1%2C0)%20%5Cto%20(1%2C1)%20%5Cto%20(2%2C1)%20%5Cto%20(2%2C2))
：
- 方向变化为：下
右（第 1 次转向）
下（第 2 次转向）
右（第 3 次转向）。共转向 3 次。
因此，最少转向次数为 2。
加载中...