BZOJ-2346: [Baltic 2011]Lamp

Description

于是他强大的脑力可以使某个格子上的线路从\变为/，或者从/变为\。2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。如果无法变亮，输出“NO SOLUTION”。


诶？？好像路线不能够通过一个格子的两个方向啊。。。也就是说可以连边求最短路。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t;
char st[710];
int head[600*600],to[1001000],nxt[1001000],f[1001000],cnt;
void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
struct node {int x,dis;};
bool operator <(node x,node y){return x.dis>y.dis; }
int dis[600*600],num[600*600];
priority_queue<node>q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",st+1);
        for(int j=1;j<=m;++j)
        {
            if(st[j]=='/')
            {
                add((i-1)*(m+1)+j,i*(m+1)+j+1,1);
                add(i*(m+1)+j+1,(i-1)*(m+1)+j,1);
                add(i*(m+1)+j,(i-1)*(m+1)+j+1,0);
                add((i-1)*(m+1)+j+1,i*(m+1)+j,0);
            }
            else
            {
                add((i-1)*(m+1)+j,i*(m+1)+j+1,0);
                add(i*(m+1)+j+1,(i-1)*(m+1)+j,0);
                add(i*(m+1)+j,(i-1)*(m+1)+j+1,1);
                add((i-1)*(m+1)+j+1,i*(m+1)+j,1);
            }
        }
    }
    memset(dis,0x3f,sizeof dis);
    s=1,t=(n+1)*(m+1); dis[s]=0;
    q.push((node){s,0}); int x,y;
    while(!q.empty())
    {
        x=q.top().x; y=q.top().dis; q.pop();
        if(!num[x])
        {
            num[x]++;
            for(int i=head[x];i;i=nxt[i])
                if(dis[to[i]]>y+f[i])
                {
                    dis[to[i]]=y+f[i];
                    q.push((node){to[i],dis[to[i]]});
                }
        }
    }
    if(dis[t]==0x3f3f3f3f) puts("NO SOLUTION");
    else printf("%d\n",dis[t]);
    return 0;
}