电路维修


解题思路

这题就是spfa
将每个格点看做节点
然后如果为 \
就说明左上到右下有一条无向边
权值为0（因为无需旋转）
左下到右上有一条无向边
权值为1（因为需旋转）
如果为 /
就说明左下到右上有一条无向边
权值为0（因为无需旋转）
左上到右下有一条无向边
权值为1（因为需旋转）

AC代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,tot,end,c[2500005],d[2500005],head[2500005];
deque<int>p;
struct node
{
   
	int to,next,w;
}a[5000005];
void add(int x,int y,int z)//双向
{
   
	a[++tot]=(node){
   y,head[x],z};
	head[x]=tot;
	a[++tot]=(node){
   x,head[y],z};
	head[y]=tot;
}
void spfa()//spfa最短路
{
   
	p.push_back(1);
	for(int i=2;i<=(n+1)*(m+1);i++)d[i]=2147483647;
	while(p.size())
	{
   
		int x=p.front();
		p.pop_front();
		for(int i=head[x];i;i=a[i].next)
		 if(d[x]+a[i].w<d[a[i].to])
		 {
   
		 	d[a[i].to]=d[x]+a[i].w;
			if(c[a[i].to]==0)
		 	{
   
		 		c[a[i].to]=1;
		 		if(!a[i].w)p.push_front(a[i].to);
		 		else p.push_back(a[i].to);
		 	}
		 }
		c[x]=0;
	}
}
int main()
{
   
	int T;
	scanf("%d",&T);
	while(T--)
	{
   
		memset(head,0,sizeof(head));
		memset(c,0,sizeof(c));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)//输入
		{
   
			string s;
			cin>>s;
	 		for(int j=1;j<=m;j++)
	 	 	if(s[j-1]=='/')
	 	 	{
   
	 	 		add(j+1+(i-1)*(m+1),j+i*(m+1),0);
	 	 		add(j+(i-1)*(m+1),j+1+i*(m+1),1);
		 	}
		 	else
			 {
   
		 		add(j+1+(i-1)*(m+1),j+i*(m+1),1);
	 	 		add(j+(i-1)*(m+1),j+1+i*(m+1),0);
			 }
		}
		end=(n+1)*(m+1);
		spfa();
		if(d[end]==2147483647)printf("NO SOLUTION");
		else printf("%d",d[end]);
		printf("\n");
	}
	return 0;
}

谢谢