bzoj2346[Baltic 2011]Lamp

kaywang

　　

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&#43;堆可以秒过，但是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;
head=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.next)
if (dist[now]+e.v<dist[e.to])
{
dist[e.to]=dist[now]+e.v;
if (!flag[e.to])
{
if(dist[now]>=dist[e.to])
{
q[t]=e.to;
flag[e.to]=1;
t=(t-1+mod)%mod;
}else
{
w=(w+1)%mod;
q[w]=e.to;
flag[e.to]=1;
}
}
}
flag[now]=0;
}
}
int main()
{
scanf(&quot;%d%d&quot;,&n,&m);
if ((n+m)&1)
{
printf(&quot;NO SOLUTION&quot;);
return 0;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
ch=' ';
while (ch!='/' && ch!='\\' ) scanf(&quot;%c&quot;,&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(&quot;%d\n&quot;,dist[(n+1)*(m+1)]);
}