算法

双端队列+广搜

这种方法完全按照dijkstra算法的原型来写，根堆优化版本契合度相当高，其中需要注意的几点
1.只有出队的时候才可以确定该点是最短距离， 顺便标记一下。
2.由于一个点可能被更新多次，我们可以把每一次距离比之前短的点入队，而没有任何影响，因为出队的时候已经把该点标记了一下。
3.\转义字符。
4.善于发现，有些点是永远不可能经过的，因为走的是对角线，因此每一次走横纵坐标都加1，因为起点横纵坐标之和为偶数因此只会经历横纵坐标为偶数的点，如果一个点横纵坐标为奇数点，则一定不会被经历过。

blablabla

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 510;

char g[N][N];
bool st[N][N];
int dist[N][N];

int n, m;

int bfs()
{
    deque<PII> q;
    q.push_front({0, 0});
    memset(st, false, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[0][0] = 0;
    int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};
    int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1};
    char init[5] = "\\/\\/";
    while(q.size())
    {
        auto t = q.front();
        q.pop_front();

        if(st[t.x][t.y])continue;
        st[t.x][t.y] = true;
        for(int i = 0; i < 4; i ++)
        {
            int a = dx[i] + t.x, b = dy[i] + t.y;
            if(a < 0 || a > n || b < 0 || b > m) continue;
            int ia = t.x + ix[i], ib = t.y + iy[i];
            //if(ia < 0 || ia >= n || ib < 0 || ib >= m)continue;
            int w = dist[t.x][t.y] + (g[ia][ib] != init[i]);
            if(g[ia][ib] == init[i])
            {
                dist[a][b] = dist[t.x][t.y];
                q.push_front({a, b});
            }
            else if(w < dist[a][b])
            {
                dist[a][b] = w;
                q.push_back({a, b});
            }
        }



    }
    return dist[n][m];
}

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

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