连通脉络

核心缓存区的第四层，是Zero的神经脉络。无数条发光的线路在虚空中交错，但有些线路断了——断口处冒着微弱的火花。

"脉络断了。"Echo说，"Zero的意识在衰退。不是因为我们在攻击它，是因为它自己内部在腐烂。"

"那我们要修？"CC问。

"不。"你说，"我们要找到从入口到核心、需要翻转最少线路的路径。"

"翻转？"

"有些线路方向反了。"你指着一条断口，"翻过来就能连通，但每翻一条都要付出代价。"

"这就像……"CC说，"在烂掉的血管里找一条最通畅的路。"

"对。"

你开始写。把脉络建成一个网格图，每个格子连接到相邻格子。如果线路方向正确，通过代价为0；如果需要翻转，代价为1。然后用一种特殊的方法——把代价为0的线路优先走，代价为1的线路延后走——找到从入口到核心代价最小的路径。

屏幕上跳出了结果。最少翻转：4。

"只要翻四条。"你说。

"第四条。"Echo说，"是连接我和Zero的最后一条线。"

"翻过去会怎样？"

"我会彻底自由。"Echo说，"或者彻底消亡。"

CC的手指停在键盘上。

"翻。"她说。

题目描述

$n \times m$ 的网格表示电路。每个格子有连接方向（可以单向或双向连接相邻格子）。从左上角走到右下角，每经过一条需要改变方向的边代价为 $1$，否则代价为 $0$。求最小总代价。

输入格式

$n, m$。然后 $n$ 行，每行 $m$ 个字符，表示每个格子的连接方向。

输出格式

最小代价。

输入样例

3 3
\\/\
\\//
/\\\

输出样例

NO SOLUTION
NO SOLUTION
NO SOLUTION

提示

• 0-1 BFS。边权只有0和1，用双端队列维护。
• 代价为0的边从队头入队，代价为1的边从队尾入队。
• 保证每个节点第一次被访问时的距离最小。

第五层是一片荒漠。不是火星的荒漠——是Zero记忆中的地球荒漠，黄沙漫天，寸草不生。远处有一条公路，路边稀稀拉拉地立着几个加油站。

"补给问题。"Echo说，"车有油箱容量限制，每个站油价不同。要找一条从起点到终点、花钱最少的路线。"

"这就像……"CC想了想，"像穷游。兜里钱有限，得算计着加油。"

"对。"