Description
2255是一个傻X，他连自己家灯不亮了都不知道。
某天TZ大神路过他家，发现了这一情况，
于是TZ开始行侠仗义了。
TZ发现是电路板的问题，
他打开了电路板，发现线路根本没有连上！！
于是他强大的脑力可以使某个格子上的线路从\变为/，
或者从/变为\。
2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮，输出“NO SOLUTION”。
n,m<=500
Input
Output
Sample Input
3 5
\\/\\
\\///
/\\\\
\\/\\
\\///
/\\\\
Sample Output
1
……我是弱渣……原来以为是各种流乱搞，结果ksy学长告诉我是最短路
如果符号是“/”左下方的点向右上方的点连边权为0的边，左上方向右下方连边权为1的边
如果符号是“\”左上方的点向右下方的点连边权为0的边，左下方向右上方连边权为1的边
然后上最短路……别忘了加双向边
25w的点Dj+堆可以秒过，但是SPFA呵呵呵……不过我有特殊的优化SPFA的方法
要用SLF优化，就是更新的时候如果当前更新的dist比正在做的dist小，就把它放在队头。具体看代码，还不会的自行百度
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 127/3
#define mod 1000007
using namespace std;
struct edge{
int next,to,v;
}e[3000010];
int cnt;
int head[260000];
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].v=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void insert(int u,int v,int w)
{
ins(u,v,w);
ins(v,u,w);
}
int n,m,t,w=1;
char ch;
int dist[260000];
bool flag[260000];
int q[mod];
inline void spfa()
{
memset(dist,inf,sizeof(dist));
int now;q[1]=1;dist[1]=0;flag[1]=1;
while (t!=w)
{
t=(t+1)%mod;
now=q[t];
for (int i=head[now];i;i=e[i].next)
if (dist[now]+e[i].v<dist[e[i].to])
{
dist[e[i].to]=dist[now]+e[i].v;
if (!flag[e[i].to])
{
if(dist[now]>=dist[e[i].to])
{
q[t]=e[i].to;
flag[e[i].to]=1;
t=(t-1+mod)%mod;
}else
{
w=(w+1)%mod;
q[w]=e[i].to;
flag[e[i].to]=1;
}
}
}
flag[now]=0;
}
}
int main()
{
scanf("%d%d",&n,&m);
if ((n+m)&1)
{
printf("NO SOLUTION");
return 0;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
ch=' ';
while (ch!='/' && ch!='\\' ) scanf("%c",&ch);
if (ch=='\\')
{
insert((i-1)*(m+1)+j+1,i*(m+1)+j,1);
insert((i-1)*(m+1)+j,i*(m+1)+j+1,0);
}
else if (ch=='/')
{
insert((i-1)*(m+1)+j,i*(m+1)+j+1,1);
insert((i-1)*(m+1)+j+1,i*(m+1)+j,0);
}
}
spfa();
printf("%d\n",dist[(n+1)*(m+1)]);
}