Description
2255是一个傻X，他连自己家灯不亮了都不知道。
某天TZ大神路过他家，发现了这一情况，
于是TZ开始行侠仗义了。
TZ发现是电路板的问题，
他打开了电路板，发现线路根本没有连上！！
于是他强大的脑力可以使某个格子上的线路从\变为/，
或者从/变为\。
2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮，输出“NO SOLUTION”。
n,m<=500
Sample Input
3 5
\\/\\
\\///
/\\\\
\\/\\
\\///
/\\\\
Sample Output
1
Solution
考虑当前格子$(i,j)$，若当前格子为$'\'$，那么$(i,j)$到$(i+1,j+1)$的花费为0，$(i+1,j)$到$(i,j+1)$的花费为1.
反之亦然。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define N (2009)
#define id(x,y) (x-1)*(m+1)+y
using namespace std; struct Edge{int to,next,len;}edge[N*N];
struct Node
{
int num,dis;
bool operator < (const Node a) const {return dis>a.dis;}
};
int n,m,c,a[N][N],dis[N*N],vis[N*N];
int head[N*N],num_edge;
char s[N];
priority_queue<Node>q; void add(int u,int v,int l)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
edge[num_edge].len=l;
head[u]=num_edge;
} void Dijkstra(int s)
{
memset(dis,0x7f,sizeof(dis));
dis[s]=; q.push((Node){s,});
while (!q.empty())
{
Node x=q.top(); q.pop();
if (vis[x.num]) continue;
vis[x.num]=true;
for (int i=head[x.num]; i; i=edge[i].next)
if (!vis[edge[i].to] && dis[x.num]+edge[i].len<dis[edge[i].to])
{
dis[edge[i].to]=dis[x.num]+edge[i].len;
q.push((Node){edge[i].to,dis[edge[i].to]});
}
}
} int main()
{
scanf("%d%d",&n,&m);
for (int i=; i<=n; ++i)
{
scanf("%s",s);
for (int j=; j<=m; ++j)
a[i][j]=(s[j-]=='\\')?:;
}
for (int i=; i<=n; ++i)
for (int j=; j<=m; ++j)
{
if (a[i][j]==)
{
add(id(i,j),id(i+,j+),); add(id(i+,j+),id(i,j),);
add(id(i+,j),id(i,j+),); add(id(i,j+),id(i+,j),);
}
else
{
add(id(i,j),id(i+,j+),); add(id(i+,j+),id(i,j),);
add(id(i+,j),id(i,j+),); add(id(i,j+),id(i+,j),);
}
}
Dijkstra();
if (dis[id(n+,m+)]>1e9) puts("NO SOLUTION");
else printf("%d\n",dis[id(n+,m+)]);
}