背景
题意
给定一个 \(r \times c\) 的网格，分别为字符左右斜杠表示电路的方向。电流可以经过电路和格点流动。每个格子可以自由旋转任意次，每次只能旋转 \(90^\circ\) 。求从左上角的格点到右下角的格点有电流经过的最小旋转次数。若电流不能到达输出 \(\textrm{NO SOLUTION}\) 。
解法
显然每个格子只可能是不动或者旋转一次的，否则必然不优。
考虑怎么建图。不妨考虑把所有的格点形成一个 \((r+1) \times (c+1)\) 的点阵，分别从 \(1\) 到 \((r+1) \times (c+1)\) 编号。这样就可以考虑对每个网格的对角线连边了。由于本身就存在电路的对角线不需要移动，所以建 \(0\) 边；若所在网格的电路与当前的对角线垂直，则沿着任意方向旋转一次就可以有电流流经，于是建 \(1\) 边。
然后就是跑最短路了。
堆优化 \(dijkstra\) 当然是可以过的，但是不够快。可以考虑线段树优化。这里不多讲了。
如果你要用那个死了的算法的话，显然网格图能把你卡飞。
由于边权只有 \(1\) 和 \(0\) 两种，考虑 \(0-1\) \(bfs\) （双端队列 \(bfs\) ）。做法是 \(0\) 边放进队首， \(1\) 边放进队尾。其他的细节和那个死了的算法没有啥区别。唯一的区别是不用判断能不能松弛，大力取 \(min\) 就是了。
细节
\(1.\) 请务必务必务必建无向边！！！
\(2.\) 有字符串读入建议用 \(cin\) 。读进来立马建好边，注意从 \(0\) 开始标号。
\(3.\) 记得初始化 \(dis\) 为\(inf\) ，后面还要判无解。