开关路障的最短时间

题目描述

深夜的实验室通道被划成 $n\times m$ 个格子，保安机器人从入口 $(1,1)$ 赶往控制台 $(n,m)$。机器人每次只能向右或向下移动一格，每次移动耗时 $1$。通道中有三类格子：

• $0$：常开，可以随时进入；
• $1$：常闭，无法进入；
• $2$：带有门禁，只有在当前时间为偶数（从 $0$ 计时）时可以进入；
• $3$：带有门禁，只有在当前时间为奇数时可以进入。

机器人起步时刻为 $0$，请计算它最早能在第几时刻到达控制台；如果无法到达，输出 $-1$。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示各格子的类型。

入口和控制台所在格子不会是常闭格。

输出格式

输出一个整数，表示到达控制台的最短时间；若无法到达，输出 $-1$。

输入输出样例 #1

输入 #1

3 4
0 2 0 0
0 1 3 0
0 0 0 0

输出 #1

6

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 50$。EOF