题目描述
Description
2255是一个傻X，他连自己家灯不亮了都不知道。
某天TZ大神路过他家，发现了这一情况，
于是TZ开始行侠仗义了。
TZ发现是电路板的问题，
他打开了电路板，发现线路根本没有连上！！
于是他强大的脑力可以使某个格子上的线路从\变为/，
或者从/变为\。
2255不会电路（因为他什么都不会），但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮，输出“NO SOLUTION”。
n,m<=500
Sample Input
3 5
\\/\\
\\///
/\\\\
Sample Output
1
题目分析
将网格图的每一个格点看作一个点
然后按着原图的方向连一条边权为0的边 逆着原图的方向连一条边权为1的边
跑堆优化spfa即可
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
char s[600];
int tot;
int head[500000],net[3000000],to[3000000],val[3000000];
void add(int x,int y,int c)
{
net[++tot]=head[x],head[x]=tot,val[tot]=c,to[tot]=y;
net[++tot]=head[y],head[y]=tot,val[tot]=c,to[tot]=x;
}
int dis[370000];
bool vis[370000];
struct cmp
{
bool operator()(const int &a,const int &b)
{
return dis[a]>dis[b];
}
};
void spfa()
{
priority_queue<int,vector<int>,cmp>q;
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
q.push(1),vis[1]=1,dis[1]=0;
while(q.size())
{
int tmp=q.top();
q.pop();
vis[tmp]=0;
for(int i=head[tmp];i;i=net[i])
if(dis[to[i]]>dis[tmp]+val[i])
{
dis[to[i]]=dis[tmp]+val[i];
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
}
void work()
{
tot=0;
memset(head,0,sizeof head);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",&s[0]);
for(int j=1;j<=m;j++)
{
int tmp=(i-1)*(m+1);
if(s[j-1]=='\\') add(tmp+j,(j+1+m+1)+tmp,0),add(tmp+j+1,tmp+j+m+1,1);
else add(tmp+j,(j+1+m+1)+tmp,1),add(tmp+j+1,tmp+j+m+1,0);
}
}
spfa();
if(dis[(n+1)*(m+1)]==0x3f3f3f3f) printf("NO SOLUTION\n");
else printf("%d\n",dis[(n+1)*(m+1)]);
}
int t;
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++) work();
}
