双端队列+bfs

在这题中把每一个交叉点看成一个节点，起点是（0，0），每次移动转移只能沿着对角线，因此每次坐标要么加2，要么减2，要么不变，所以易得所能到达的坐标的x、y之和一定跟起点是x、y之和具有相同的奇偶性，即都是偶数，因此若终点的坐标之和是奇数，那么NO SOLUTION。

从一个节点到另一条节点需要经过一条对角线，当这两个节点围成的那个方格中的对角线已经连接这两个点，那么这两个节点间的边权为0，否则为1于是这幅图就抽象成了一幅边权为01的无向图，题目就成了只包含边权为01的最短路问题，

与普通的宽搜只有一点不一样，普通的宽搜是将更新的点放到队尾去，但是在这题中，如果扩展出来的边的权重是0则插到队头，否则插到队尾。

所有bfs能求最短路问题的正确性可以通过转化成Dijkstra算法能解决的问题来证明，（因为Dijkstra算法是正确的，因此如果能转化成Dijkstra算法，
则说明原算法就是正确的。
在这道题中，如果根据刚才的插入方式同样可以保证队列是单调的，而且可以保证两段性

C++ 代码

#include <iostream>
#include <deque>
#include <algorithm>
#include <cstring>

#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];

int bfs()
{
    memset(st , 0 , sizeof st);
    memset(dist , 0x3f , sizeof dist);
    deque<PII> q;

    q.push_back({0 , 0});
    dist[0][0] = 0;

    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};//一个点周围的四个方格坐标偏移量

    char cs[5] = "\\/\\/";//一个点可以到周围四个点的对角线

    while(q.size())
    {
        auto t = q.front();
        q.pop_front();

        int x = t.x , y = t.y;
        if(x == n && y == m) return dist[x][y];

        if(st[x][y]) continue;
        st[x][y] = true;

        for(int i = 0 ; i < 4 ; i++)
        {
            int a = x + dx[i] , b = y + dy[i];
            if(a >= 0 && a <= n && b >= 0 && b <= m)
            {
                int ca = x + ix[i] , cb = y + iy[i];
                int w = (g[ca][cb] != cs[i]);
                int d = dist[x][y] + w;
                if(d < dist[a][b])
                {
                    dist[a][b] = d;
                    if(w)   q.push_back({a , b});//如果需要转向，则说明距离+1，插入队尾
                    else q.push_front({a , b});//如果不用转向，则距离不改变，直接推到队头
                }                              //这样的操作可以保证两段性，即一段x,...,x,接下来一段x+1,x+1...x+1
            }
        }

    }
}

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

    while(T--)
    {
        cin >> n >> m;
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m ; j++)
                cin >> g[i][j];

        if(n + m & 1) puts("NO SOLUTION");
        else cout << bfs() << endl;
    }
    return 0;
}