心路历程

这是孵化器实验室一轮考核第二期的E题，旨在考查大家对bfs/dfs和剪枝算法的应用

题目背景

一个梨先生患有心肌梗，且是远近闻名的自闭患者。

为了让梨先生继续当工具人，他的父亲梨司令为他请来了声名远播的 homo 心理医生，Kaoru先生。

Kaoru 先生决定通过梳理和解决梨先生的各个心理问题节点来进行治疗的补完。

题目描述

为了便于理解，我们将这个治疗过程具象为一个$m \times m$的矩阵，其中每一个节点代表梨先生的每一段记忆，其类型包括痛苦的，快乐的，又或是尚未具有情绪和感受的。Kaoru 在其中移动代表通过某个记忆进行治疗，Kaoru 先生现在要通过从这个矩阵的左上角走到右下角的方式来完成治疗。

每一次移动，Kaoru 先生必须保证当前节点的记忆是痛苦或快乐的（这样可以便于下次治疗开始时延续话题）， Kaoru 只能向上、 下、左、 右四个方向前进。当 Kaoru 从一段记忆走向另一段记忆时，如果两段记忆的类型相同（都是痛苦的或者都是快乐的），那 Kaoru 不需要花费精力进行过度；如果不同，则 Kaoru 需要花费 $1$点精力。

另外， Kaoru 可以花费 $2$ 点精力使用高级话聊让下一个尚未拥有情绪和感受的记忆点暂时变为他所指定的类型（快乐或痛苦）。但这个技能不能连续使用， 而且这个技能的持续时间很短，也就是说，如果 Kaoru 使用了这个技能，走到了这个暂时快乐或痛苦的记忆点上，他就不能继续使用技能； 只有当他离开这个位置，走到一个本来就快乐或痛苦的记忆点上的时候，他才能继续使用这个技能，而当他离开了这个位置（施展技能使得变为快乐或痛苦的记忆点）时，这个记忆点恢复为尚未拥有情绪和感受的。

现在 Kaoru 要从矩阵的最左上角，走到矩阵的最右下角，求花费的最少精力是多少？

不包含背景的概述

有一个$m×m$的矩阵，矩阵上每一个格子可能是类型 1、类型 2 或类型 3 的。你现在要从矩阵的最左上角走到矩阵的最右下角。

任何一个时刻，你所站在的位置必须是有类型 1 或 2 的（不能是类型 3 的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的类型相同，那你不需要花费精力；如果不同，则你需要花费 1点精力。

另外， 你可以花费 2 点精力施展话术让下一个类型 3 的格子暂时变为你指定的类型。但这个话术不能连续使用， 而且这个话术的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时不是类型 3 的格子上，你就不能继续使用话术； 只有当你离开这个位置，走到一个本来就非类型 3 的格子上的时候，你才能继续使用这个话术，而当你离开了这个位置（施展话术使得变为类型 1 或 2 的格子）时，这个格子恢复为类型 3。

现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少精力是多少？

输入格式

第一行包含两个正整数$m, n$，以一个空格分开，分别代表矩阵的大小，矩阵上本就痛苦或快乐的记忆点的数量。

接下来的$n$行，每行三个正整数$x, y, c$， 分别表示坐标为$(x,y)$的记忆点是痛苦的或快乐的$c$。

其中$c=1$ 代表痛苦，$c=0$ 代表快乐。 相邻两个数之间用一个空格隔开。 矩阵左上角的坐标为$(1, 1)$，右下角的坐标为$( m, m)$。

矩阵上其余的格子都是尚未具有情绪和感受的。保证矩阵的左上角，也就是$(1, 1)$ 一定是快乐或痛苦的。

输出格式

一个整数，表示花费的精力的最小值，如果无法到达，输出$-1$。

样例

样例输入

5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0

样例输出

-1

提示

样例说明

从$( 1, 1)$走到$( 1, 2)$,不花费精力

从$( 1, 2)$走到$( 2, 2)$,花费$1$点精力

施展技能将$( 2, 3)$变为痛苦,并从$( 2, 2)$走到$( 2, 3)$花费$2$ 精力

从$( 2, 3)$走到$( 3, 3)$不花费精力

从$( 3, 3)$只能施展技能到达$( 3, 2),( 2, 3),( 3, 4),( 4, 3)$

而从以上四点均无法到达$( 5, 5)$,故无法到达终点,输出$-1$

数据规模与约定

对于 $30\%$的数据, $1 ≤ m ≤ 5, 1 ≤ n ≤ 10$。

对于 $60\%$的数据, $1 ≤ m ≤ 20, 1 ≤ n ≤ 200$。

对于 $100\%$的数据, $1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000$。