题目描述
达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障，导致无法启动。
电路板的整体结构是一个R行C列的网格（R,C≤500），如下图所示。
每个格点都是电线的接点，每个格子都包含一个电子元件。
电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。
在旋转之后，它就可以连接另一条对角线的两个接点。
电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。
达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。
她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。
不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。
输入格式
输入文件包含多组测试数据。
第一行包含一个整数T，表示测试数据的数目。
对于每组测试数据，第一行包含正整数R和C，表示电路板的行数和列数。
之后R行，每行C个字符，字符是”/”和”"中的一个，表示标准件的方向。
输出格式
对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。
如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。
数据范围
$1≤R,C≤500$
$1≤T≤5$
只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。
样例
输入样例：
1
3 5
\\/\\
\\///
/\\\\
输出样例：
1
样例解释
样例的输入对应于题目描述中的情况。
双端队列+广度优先搜索
首先把电路板上每一个格子点(交叉点)看作无向图中的节点,我们认为两个节点x和y是某个小方格的两个对角,那么如果说x和y的线段’',那么我们可以认为边权为0,反之如果x和y线段是’/’,那么我们的边权视为1,说明要旋转一次才能够连上.
现在我们得到了一张完美的边权0或1的无向图,那么和普通广搜一样,我们唯一的改变就是,如果说当前新状态的边权为0,那么我们就放到队头先走,因为我们要满足两端性和单调性,而为了这个单调性,如果说当前新状态边权为1,那么我们就只能压入到队尾.
具体小细节就看代码吧.hh
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=510;
const int dxy1[4][2]= {{1,1},{-1,-1},{1,-1},{-1,1}},dxy2[4][2]= {{1,1},{0,0},{1,0},{0,1}};//两种不同走法(因为两种线路),所以要两个方向数组
struct node
{
int x,y;
};
int t,n,m,ans=1e8,dis[N][N];
char s[N][N];
bool vis[N][N];
deque<node> q;//双端队列
int check(int x,int y)
{
return x>=0 && x<=n && y>=0 && y<=m;//范围内
}
void bfs()
{
vis[0][0]=1;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));//初始化最大值
q.push_front(node {0,0});//0开始,是因为读入的不是坐标,而是两种线路,然后你就会发现其实坐标点是要从0开始的,当然你n+1,m+1也是可以的
dis[0][0]=0;
while(q.size())
{
node now=q.front();
q.pop_front();
fir(i,0,3)//四种方向
{
int tx=now.x+dxy1[i][0],t1=now.x+dxy2[i][0];//如果是'\'
int ty=now.y+dxy1[i][1],t2=now.y+dxy2[i][1];//如果是'/'
int tt=(s[t1][t2] != (i<=1? '\\':'/'));//转义字符要双写,这里用到了三目运算符
if(check(tx,ty) && dis[tx][ty]>dis[now.x][now.y]+tt)//check成功,并且当前值更加优秀
{
dis[tx][ty]=dis[now.x][now.y]+tt;
if(tt)
q.push_back(node {tx,ty});//边权值为1
else
q.push_front(node {tx,ty});//边权值为0
}
}
}
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
fir(i,1,n)
fir(j,1,m)
cin>>s[i][j];
bfs();
if(dis[n][m]<1e8)//如果找到了方案
cout<<dis[n][m]<<endl;
else
cout<<"NO SOLUTION"<<endl;
}
return 0;
}
y总 加了st数组 为什么还能保证让一个点会被更新多次
1->(0)->2
->(1)->3
2->(0)->3
问，1->3的最短距离是多少？
如果按原始的bfs+st,距离是1。按双端队列方式处理，距离是0.
双端队列广搜一个点第一次被扩展到，是不是就是它到起点的最短距离呢
是的，因为具有单调性
不是的，第一次出队才是。已经搞懂了
出队不就是扩展吗？入队貌似是更新
请问这一步：
int tt=(s[t1][t2] != (i<=1? ‘\‘:’/’));
是什么意思呢orz
从左向右看，显示判断i<=1 是否为真，之后，如果判断s和后面是否相等，相等tt=1，否则为0
我的理解：这个代码没有问题吧，仔细模拟一下发现加vis防止多次访问其实也是没用的，反正前面更新过了，后面就不会再更新了，一个点的入队次数也最多为2啊（如果一个点入队了两次，只有前面那次有用）
你是对的，从 逻辑角度来看，那个是否进过队列是没用的，因为最小的肯定最早被算出来，后面与它PK都是徒劳的。但从优化角度来看，记录ST，可以防止无用的PK，性能会更快。
您这个不是双端队列BFS,而是双端队列优化SPFA吧
我觉得楼下说的有道理，你这种写法确实不是O(n)的，一个元素可能重复入队，比如说一个点可能从左上或者右上走来都是同样的代价且边权都为0，这时这个点会入两次对，并且扩展两次。虽说保证了第一次出队就是最小值，但没有保证一个元素只会扩展一次。可能需要加个vis数组，来保证只扩展一次
请问大佬; 为什么存在路通不了的情况？
比如说你的起点是(0,0)，终点是（1，2）这两个点不可能有通路的，用起点和终点的坐标的奇偶性就可以判断，因为每一个操作不会改变奇偶性
当$m+n+1$的值为偶数时，无解
不是把0压入队首，1压入队尾已经保证了单调性，为什么还要记录起点到该点的距离，这与spfa有什么区别?
肯定要记录距离啊,这道题目就是要你求出距离啊.
不是这个意思，你可以在队列中的元素就记录这个距离，第一个到的结果最优
再阐述一下，也就是队列具有单调性，因此第一个到达的状态就是最优解，而你的代码存在更新这一步操作，也就是专业化所说的松弛，所以就与spfa没有太大差别了，唯一的差别就是双端队列和普通队列。
队列的确有单调性,而且松弛操作就是三角不等式没错啊,与SPFA没有多大差别,的确没有多大差别啊,SPFA就是队列实现,而且双端队列和普通队列的差别,也就是SPFA的SLF优化,也没什么毛病啊.BFS具有最优解性质,也就是步骤单调性,木有毛病,在队列里面多开一个元素记录,是可以的,但是放在外面,一个dis数组也木有问题吧,这个看个人习惯就好了.
而且结构体的效率,是低于数组效率的.
spfa不是$O(n^2)$,你没理解我的问题,lyd说书上的双端队列bfs是$O(n)$的
既然其余板子都是照spfa的，那么不同点就在双端队列着了
SPFA准确来说复杂度是$O(kn)$,然后在最坏的菊花图上面是$O(n^2)$
而且我这不是SPFA啊!
你还是没理解我的问题，lyd说只有01为边权的图上的双端队列bfs与普通队列的bfs不同在双端，其余照旧，于是我就真的照旧了，结果?了，然后我才发现要有这个dis数组才行，而有了dis数组又和接下来的spfa很类似，区别在双端队列，那么spfa的时间复杂度是显然的，关键在这个双端队列，我不能解释它了
01边权,先0再1,因为只有两种选择,所以$O(n)$.
01边权,先0再1,因此$O(n)$,而怎么先0再1,自然就是双端,队头放0,队尾放1.
但是如果被更新不会再次入队吗
好奇怪啊
怎么不回我了，今天我们考试考了双端队列bfs,但是我还是不能认可它
我承认我自己很喜欢纠结这些毫无意义的东西，别人背一背就过去了，但是我不理解它，我就不相信它，今天我选拔考试考的太差了，还有三次，我知道你没有义务一定要帮助我搞懂，但是还是希望你帮我一把。
帮你是应该的。
如果被更新不会再次入队吗？为什么会再次入队呢？入队一次后，再次入队就是存在回路，但是这里的回路无法形成，因为唯一的回路是1010，我们这里是1在前面0在后面，怎么说也是1100，所以不存在回路。
双端可以认为是存在优先级的搜索，因为只有10，而且1在前面，0在后面。
回路是什么意思？还有10应该反了？除此之外，还存在一个问题，就是双端队列已经保证了优先级，为什么我们还需要用一个dis数组取存呢？而且前面章节的广搜就已经存在优先级了，没有再用一个数组取保存答案。
所谓的优先级只不过是搜索的顺序。
dis数组存储的路径长度。
回路就是，我从x节点出发，往外面走，然后走着走着我走回来了，又回到了x节点，这一路上经过的边构成回路。
祝你选拔通过。
话说你是高中OIer吗？我记得只有高中部才会选拔吧。
我好像对bfs的理解有误，确实存在单调性，其实双端队列同样保证了这个单调性，而这个dis数组是不应该的，因为双端队列的入队操作已经保证了靠前的更加优秀，但是我理解成了，只要入队就是最优，事实上是第一次取出来的状态才是最优的，因此根本不需要dis数组，所以推广开来，bfs，优先队列bfs,dijistra,都不需要dis数组，因为队列已经保证了单调性，这才是它们的共性。
我是g2老年noip选手，我今天t3写挂了，本来想到40分暴力，结果突然不记得tarjan了，全场切t1.而我就写了个35分暴力，其他部分贪心，t2写了个众人暴力，所以今天的成绩无望了，真的很好奇我g1一年努力搞竞赛白搞了，别人边搞学科边搞竞赛，到头来，两个都比我搞得好，这就是差距啊。
是的，有的时候，只要控制x,y坐标，但是有些大佬懒得写结构体，所以就把dis数组单独拿出来了。
一场比赛失常不可怕，稳定心态，努力总会有收获了。
出成绩了，我又掉rank了，别人day1萎了，今天力挽狂澜，我差了70多分,还有两次，怕是这把不行了，因为我t2爆0了(为什么就是我没有思路啊),t1是大众分，t3分数还可以,所以排名还不是很靠后
稳定下心态，拿稳暴力分。一般来说暴力分不要太长时间，先求稳，然后求分数高，虽然我知道题目怎么样，但是还是一句话，不让自己后悔，不要打爆任何一道题目。
t1的20分暴力我是最后30分钟想到的,t2我完全没有思路，t3我先拿了递推的分，再想办法贪心又拿了20分，我不知道网络流都比写网络流的分数高。
暴力分基本上是最后两个小时补上的，前两个小时基本上花在思路上，根本没时间对拍，尽管我不会,下一次考试是15号，成绩差不多可以保送25班了，但愿noip不要挂，noip凉了是真的凉了。
祝你成功。
while(1) rp++;
thank you
int *a;
while(1)a=new int;
hh
假设队列中是{0, 0, 0, 1, 1, 1}，在下一层搜索的时候，前面三个0都有可能达到最优的状态，比如第一个0可能在下一层之后就不是最优的了.
BFS里第1行vis[0][0]=1;
下面又来一个memset，不会覆盖掉这个1吗？
是的,收到.
实际上去掉这句话没有问题.