电路维修
与BFS的不同点在于图中两点边权为0或1。如果为0，那么插入队首；如果为1，那么插入队尾。

Δ（1）方向向量千万别搞错，搞错一小时起步；
Δ（2）取出队首立马给爷出队。

#include <iostream>
#include <cstdio>
#include <deque>
#include <cstring>

using namespace std;

const int N = 510;

int n,m;
char g[N][N];
int dis[N][N];
bool vis[N][N];
char c[10] = "\\/\\/";
int dx[10] = {-1,-1,1,1},dy[10] = {-1,1,1,-1};
int xx[10] = {-1,-1,0,0},yy[10] = {-1,0,0,-1};

int bfs()
{
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));

    deque<int> x,y;
    x.push_back(0),y.push_back(0);
    dis[0][0] = 0;

    while(x.size())
    {
        int hx = x.front(),hy = y.front();
        x.pop_front(),y.pop_front();

        if(hx == n && hy == m)
            return dis[n][m];

        if(!vis[hx][hy])
        {
            for(int i = 0;i < 4;i ++)
            {
                int nx = hx + dx[i],ny = hy + dy[i],gx = hx + xx[i],gy = hy + yy[i];
                if(nx >= 0 && nx <= n && ny >= 0 && ny <= m)
                {
                    int d = dis[hx][hy] + (g[gx][gy] != c[i]);
                    if(d <= dis[nx][ny])
                    {
                        dis[nx][ny] = d;

                        if(g[gx][gy] != c[i])
                            x.push_back(nx),y.push_back(ny);
                        else
                            x.push_front(nx),y.push_front(ny);
                    }
                }
            }

            vis[hx][hy] = true;
        }
    }
}

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;
}