前置知识：
SPFA
还有一些小小的优化东东
如果不了解SLF+LLL可以先学一下 这个
因为本题暴力建图跑SPFA会T掉，所以需要这一点小小的常数优化

题解：
把每个点看成一个节点，如果本来就有那条边则边权为0，否则需要通过旋转得到的边边权为1，就是跑第一个点和最后一个点的最短路即可

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int M=3e6+10;
struct qwe{
    int x,y,z,next;
}e[M];
int dis[M],elast[M],v[M];
int id[1000][1000];
void spfa(int x)
{
    deque<int>q;
    q.push_back(x);
    v[x]=1;
    dis[x]=0;
    int num=1,sum=0;
    while(!q.empty())
    {    
        int qwe=q.front();
        while(num*dis[qwe]>sum)
        {
            q.pop_front();
            q.push_back(qwe);
            qwe=q.front();
        }
        q.pop_front();
        v[qwe]=0;
        num--;
        sum-=dis[qwe];

        for(int i=elast[qwe];i;i=e[i].next)
        {
            int k=e[i].y;
            if(dis[qwe]+e[i].z<dis[k])
            {
                dis[k]=dis[qwe]+e[i].z;
                if(v[k]==0)
                {
                    v[k]=1;
                    if(!q.empty()&&dis[k]<dis[q.front()])q.push_front(k);
                    else q.push_back(k);
                    num++;
                    sum+=dis[k]; 
                }
            }
        } 
    }
}
int k;
void add(int x,int y,int z)
{
    e[k].x=x;
    e[k].y=y;
    e[k].z=z;
    e[k].next=elast[x];
    elast[x]=k++;
}
int t,n,m;
int tot;
void clean()
{
    for(int i=1;i<=(n+1)*(m+1);i++)dis[i]=1e9,v[i]=0;
    memset(elast,0,sizeof(elast));
    tot=0;
    k=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=m+1;j++)
        {
            id[i][j]=++tot;
        }
    }

}
char x;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        clean();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                x=getchar();
                if(x!='\\'&&x!='/')x=getchar();
                if(x=='\\')
                {
                    add(id[i][j],id[i+1][j+1],0);
                    add(id[i+1][j+1],id[i][j],0);
                    add(id[i+1][j],id[i][j+1],1);
                    add(id[i][j+1],id[i+1][j],1);
                }
                else
                {
                    add(id[i][j],id[i+1][j+1],1);
                    add(id[i+1][j+1],id[i][j],1);
                    add(id[i+1][j],id[i][j+1],0);
                    add(id[i][j+1],id[i+1][j],0);                   
                }
            }
        }
        spfa(1);
        if(dis[tot]==1e9)printf("NO SOLUTION\n");
        else printf("%d\n",dis[tot]);
    }
}