//如果知道走这条路要不要改变,又怎么是最小次数:看做图,一样就不改变,不一样就改变,
//用d表示到这最少要改变的,所以d就是最小次数
//本题的权值要么是0要么是1,所以用双端队列来代替堆,少一个logn
//把所求的转到权值上,那么可以通过求权值来计算最终的结果
//dfs,bfs都是把题目看做一个特殊(用数组存的)有权图去分析求解,结点是坐标点,
//边是可走的路,权值是一样不一样,是否需要改变
//main:多组测试数据行列字符串输入,输出bfs
//bfs:初始化队列,距离,出列,四个方向判断,是否相同判断,得最小值,权值0则左端入列,1则右端入列
//(因为原理是队列中的元素是单调的才可以得到最短路径,所以这里使用双端队列来维持单调性,或用堆(优先队列)
//bfs入队条件是可以更新得到答案,不能更新答案的提前剪枝
#include<iostream>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
typedef pair<int,int>PII;
const int N=510;
int n,m;
char g[N][N];
int d[N][N];
int bfs()
{
memset(d,0x3f,sizeof d);//int 四个字节,所以所有的d都初始化为0x3f3f3f3f
deque<PII>dq;//有不同权值的用双端队列或堆来维护(bfs求最短路问题中)
dq.push_back({0,0});//初始化起点
d[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[]="\\/\\/";//四个方向的路径
while(dq.size())
{
PII t=dq.front();dq.pop_front();
int x=t.first,y=t.second;//先保存原坐标//方向和其他条件分开判断,相互独立互不干扰
//(也可以在入列的时候判断其他条件)
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)//以后这里就写不越界,题意就是从0,0走到n,m所要改变的最小次数
{//其他判断条件到里头来搞
int w=0;
int j=x+ix[i],k=y+iy[i];
if(g[j][k]!=cs[i])w=1;//路线和走的方向不一样则需要改变旋钮,权值为1,否则为0.
//(将运算结果转为权值,最后求权值的和即可)
//压入四个方向走的路,不是j,k,不是字符的坐标
if(d[a][b]>d[x][y]+w)//只有你可以更新为这条路的最小改变次数,才入队,剪枝
{//bfs入队条件是可以更新得到答案,不能更新答案的提前剪枝//最小值判断
d[a][b]=d[x][y]+w;
if(w)dq.push_back({a,b});//用双端队列代替堆(因为原理是队列中的元素是单调的才可以得到最短路径
//,因为权值只有两个,所以这里使用双端队列来维持单调性,或用堆(优先队列),
//先弹出最小的来寻找,那第一次到达的一定是最小的那个到达,那自然结果是最短路径咯
else dq.push_front({a,b});//小的往前方,大的往后方,维护双端队列的单调性
}
}
}
}
if(d[n-1][m-1]==0x3f3f3f3f)return -1;//memset按字节分配,int是四个字节,所以d初始化为0x3f3f3f3f(四个)
else return d[n][m];//题意是从0,0走到n,m
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>g[i];//输入字符串的方法
if(bfs()==-1)cout<<"NO SOLUTION"<<endl;
else cout<<bfs()<<endl;
}
return 0;
}