题目传送门

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
char ch;
int d[1010][1010];
bool v[1010][1010];
int edge[1010][1010][4];
int dx[4]={-1,-1,1,1};
int dy[4]={-1,1,-1,1};
struct node
{
	int x,y;
};
void bfs()
{
	deque<node> q;
	node t,u;
	t.x=1;
	t.y=1;
	v[1][1]=1;
	d[1][1]=0;
	q.push_front(t);
	while(!q.empty())
	{
		t=q.front();
		q.pop_front();
		for(int i=0;i<4;i++)
		{
			int xx=t.x+dx[i],yy=t.y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!v[xx][yy])
			{
				int w=d[t.x][t.y]+edge[t.x][t.x][i+1];
				if(w<d[xx][yy])
				{
					d[xx][yy]=w;
					v[xx][yy]=1;
					u.x=xx;
					u.y=yy;
					q.push_front(u);
				}
			}
		}
	}
}
void init()
{
	memset(edge,0,sizeof(edge));
	memset(v,0,sizeof(v));
}
void work()
{
	init();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>ch;
			if(ch=='/')
			{
				edge[i][j+1][3]=0;
				edge[i+1][j][2]=0;
				edge[i][j][4]=1;
				edge[i+1][j+1][1]=1;
			}
			else
			{
				edge[i][j][4]=0;
				edge[i+1][j+1][1]=0;
				edge[i][j+1][3]=1;
				edge[i+1][j][2]=1;
			}
		}
	n++,m++;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			d[i][j]=0x3f3f3f3f;
	bfs();
	if(d[n][m]<0x3f3f3f3f)
		printf("%d\n",d[n][m]);
	else
		printf("NO SOLUTION\n");
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
		work();
	return 0;
}