莫欺少年穷，修魔之旅在这开始—>算法提高课题解

保姆级注释，看不懂你炸我

双端队列+bfs PK 权值0或1的最短距离问题

思路：

1. 该题有个性质，如果是奇数点，就永远无法走到，故可提前判断
2. cs 表示该方向希望的符号，dx 表示该方向到达的点的方位，ix 表示该方向到达的符号的方位
3. st 表示已确定了最短距离的集合，dist 表示到达该点的最短距离
4. 多组测试数据，需要初始化 st 数组和 dist 数组
5. 双端队列取出的点一定是最短距离，因为后面即便再枚举到该点，也只会 d >= dist[a][b];
6. 故取出队头后，先观察是否到达终点，若到达终点，直接 return，否则，加入 st 数组集合
7. 比较实际符号与希望符号，相等为 0，不等为 1，更新该点在此方向上到达的点的最短距离
8. 若该点的最短距离比原来更小，则更新最短距离
9. 若权值为 0，则插入队头，否则，插入队尾

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 510;

int n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];

//枚举四个方向希望的符号
char cs[5]="\\/\\/";

//枚举四个方向能到达的点的方位
int dx[4]={-1,-1,1,1},dy[4]={-1,1,1,-1};

//枚举四个方向符号的方位
int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1};

int bfs()
{
    //初始化双端队列
    deque<PII> q;
    q.push_back({0,0});

    //初始化st数组
    memset(st,0,sizeof st);

    //初始化dist数组
    memset(dist,0x3f,sizeof dist);
    dist[0][0]=0;

    while(q.size())
    {
        //取出队头，一定到达该点的最短距离
        auto t=q.front();
        q.pop_front();

        int x=t.x,y=t.y;

        //到达终点，直接return
        if(x==n&&y==m) return dist[x][y];

        //放入已确定最短距离的集合中
        st[x][y]=true;

        //枚举四个方向
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];

            //超出边界，(0, 0) -> (n, m)
            if(a<0||a>n||b<0||b>m) continue;

            //该点能到达的符号的坐标
            int ga=x+ix[i],gb=y+iy[i];

            //实际符号与希望符号对比
            int w=(g[ga][gb]!=cs[i]);

            //更新该点在此方向上到达的点的最短距离
            int d=dist[x][y]+w;

            //到达该点的最短距离比原来小
            if(d<dist[a][b])
            {
                //更新该点的最短距离
                dist[a][b]=d;

                //如果权值为0，插入队头
                if(!w) q.push_front({a,b});

                //如果权值为1，插入队尾
                else q.push_back({a,b});
            }
        }
    }

    return -1;
}

int main()
{
    int T;
    cin>>T;

    while(T--) 
    {
        cin>>n>>m;

        for(int i=0;i<n;i++) cin>>g[i];

        //假如n+m是奇数，就永远都无法到达
        if(n+m&1) cout<<"NO SOLUTION"<<endl;
        else cout<<bfs()<<endl;
    }

    return 0;
}