![$Luogu$ $P4667$ $[BalticOI$ $2011$ $Day1]$ 打开灯泡 $Switch$ $the$ $Lamp$ $On$](/default/index/img?u=aHR0cHM6Ly9wMC5waXFzZWxzLmNvbS9wcmV2aWV3LzgzOC82OS8yODMvYXVzdHJhbGlhLWNhcmx0b24tcm95YWwtZXhoaWJpdGlvbi1idWlsZGluZy1yb3lhbC1idWlsZGluZy5qcGc=&w=245&h=&w=700)
链接
背景
(Baltic) (Olympiad) (in) (Informatics) (2011) (Day1) (T3) ， (Luogu) (P4667/LOJ2632) （原题面暂时无法打开）
题意
给定一个 (r imes c) 的网格，分别为字符左右斜杠表示电路的方向。电流可以经过电路和格点流动。每个格子可以自由旋转任意次，每次只能旋转 (90^circ) 。求从左上角的格点到右下角的格点有电流经过的最小旋转次数。若电流不能到达输出 ( extrm{NO SOLUTION}) 。
解法
显然每个格子只可能是不动或者旋转一次的，否则必然不优。
考虑怎么建图。不妨考虑把所有的格点形成一个 ((r+1) imes (c+1)) 的点阵，分别从 (1) 到 ((r+1) imes (c+1)) 编号。这样就可以考虑对每个网格的对角线连边了。由于本身就存在电路的对角线不需要移动，所以建 (0) 边；若所在网格的电路与当前的对角线垂直，则沿着任意方向旋转一次就可以有电流流经，于是建 (1) 边。
然后就是跑最短路了。
堆优化 (dijkstra) 当然是可以过的，但是不够快。可以考虑线段树优化。这里不多讲了。
如果你要用那个死了的算法的话，显然网格图能把你卡飞。
由于边权只有 (1) 和 (0) 两种，考虑 (0-1) (bfs) （双端队列 (bfs) ）。做法是 (0) 边放进队首， (1) 边放进队尾。其他的细节和那个死了的算法没有啥区别。唯一的区别是不用判断能不能松弛，大力取 (min) 就是了。
细节
(1.) 请务必务必务必建无向边！！！
(2.) 有字符串读入建议用 (cin) 。读进来立马建好边，注意从 (0) 开始标号。
(3.) 记得初始化 (dis) 为(inf) ，后面还要判无解。
代码
$View$ $Code$
```cpp
#include
using namespace std;
inline int read()
{
int ret=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
ret=(ret<<1)+(ret<<3)+ch-'0';
ch=getchar();
}
return ret*f;
}
const int inf=0x3f3f3f3f;
int T,r,c,dis[300005];
int num,head[300005];
char s[505];
bool vis[300005];
deque q;
struct edge
{
int ver,nxt,w;
}e[2000005];
inline void adde(int u,int v,int w)
{
e[++num].ver=v;
e[num].nxt=head[u];
e[num].w=w;
head[u]=num;
}
inline void bfs(int s)
{
q.clear();
dis[s]=0;
q.push_front(s);
while(!q.empty())
{
int x=q.front();
q.pop_front();
if(vis[x])
continue;
vis[x]=1;
for(register int i=head[x];i;i=e[i].nxt)
{
int y=e[i].ver;
if(e[i].w)
{
dis[y]=min(dis[y],dis[x]+1);
q.push_back(y);
}
else
{
dis[y]=min(dis[y],dis[x]);
q.push_front(y);
}
}
}
}
int main()
{
r=read();
c=read();
for(register int i=1;i<=r;i++)
{
scanf("%s",s);
for(register int j=1;j<=c;j++)
{
int leftup=(i-1)*(c+1)+j,leftdown=i*(c+1)+j,rightup=(i-1)*(c+1)+j+1,rightdown=i*(c+1)+j+1;
if(s[j-1]=='\')
{
adde(leftup,rightdown,0);
adde(rightdown,leftup,0);
adde(leftdown,rightup,1);
adde(rightup,leftdown,1);
}
else
{
adde(leftup,rightdown,1);
adde(rightdown,leftup,1);
adde(leftdown,rightup,0);
adde(rightup,leftdown,0);
}
}
}
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
bfs(1);
if(dis[(r+1)*(c+1)])>
