Skip to content

1037: 小可怜操纵大选

题目

题目描述

助教是个小可怜,因为她不知道要出什么机考题了。然后她发现大家上周学了搜索,欣喜若狂。那一天刚好是大选之日,她在搜索引擎输入了election 2020,开始关注自己还能不能出国读书。选情十分焦灼,小可怜越看越紧张,一怒之下关闭网页开始睡回笼觉。小可怜希望在梦中能获得操纵大选的能力。

日有所思,日有所梦。小可怜梦到自己来到了一个国家USB(United States of Bairimeng),这个国家由$m - 1$条经线和$m - 1$条纬线分隔,一共拥有$m \times m$ 个州,每个州是红州,蓝州,摇摆州中的一种。一位叫做Truden的人想要找一条路,从USB最西北角的州走到最东南角的州。

任何一个时刻,Truden不被允许出现在摇摆州。Truden只能往上下左右四个方向的州前进,当Truden从一个州走到另一个州,如果两个州的颜色相同,那么Truden不需要支付过路费,否则Truden需要支付1USB元的过路费。

但不能取道摇摆州使Truden十分苦恼,于是Truden找上了在USB做大法师的小可怜。每次只要支付2USB元,小可怜就会帮Truden暂时把一个摇摆州变成红州或者蓝州中的一种。但是要注意的是,小可怜使用魔法后,Truden可以入境一个被变色的摇摆州,但当Truden还在此州境内时,小可怜不会帮Truden把另一个摇摆州也变色,直到Truden离开此州,小可怜才同意会帮Truden再次施法。而当Truden离开了变色了的摇摆州后,这个州又将变成摇摆州。

请你帮Truden计算一下,他最少要花费多少USB元,才能从西北角的州走到东南角的州。

输入格式

第一行包含两个正整数$m,n$,以一个空格分开,分别代表USB拥有$m \times m$个州,以及摇摆州的数量是$n$

接下来的$n$行,每行三个整数$x,y,c$,相邻的两个整数由一个空格隔开,分别表示坐标为$(x,y)$的州的立场。坐标为$(x,y)$的州表示,从北往南数第$x$行,从西往东数第$y$列的那个州。如果$c = 1$,此州是蓝州,$c = 0$,此州是红州。

而其他的州均为摇摆州。数据保证西北角的州(即坐标为$(1,1)$的州)不是摇摆州。

输出格式

一个整数,表示花费的USB元的最小值。如果Truden无法到达东南角的州,请输出-1。

样例输入

样例1

5 7 1 1 0 1 2 0 2 2 1 3 3 1 3 4 0 4 4 1 5 5 0

样例2

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

样例输出

样例1

8

样例2

-1

数据范围

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

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

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

小可怜眼看各州转红,一怒之下把全国都变成蓝色的了!(此行为不影响本题,请按题面做题)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!