https://www.acwing.com/problem/content/177/ 40分

#include<bits/stdc++.h>
using namespace std;
struct node{int x, y;}a[510][510]; bool op[510][510];
struct hh{int x, y, c;};
int n, m, ans; int v[510][510];
int dx[4]={-1, -1, 1, 1}, dy[4]={-1, 1, -1, 1};
void bfs()
{
	queue<hh> q; q.push({1, 1, 0});
	memset(v, 63, sizeof(v)); v[1][1]=0;
	while(!q.empty())
	{
		auto t=q.front(); if(v[t.x][t.y]!=t.c) {q.pop(); continue;}
		if(t.x==n+1&&t.y==m+1) {ans=min(ans, t.c); q.pop(); continue;}
		
		{
			int xx=t.x, yy=t.y; 
			xx+=dx[0], yy+=dy[0];
			if(v[xx][yy]&&xx<=n+1&&yy<=m+1&&xx&&yy)
			{
				if(op[xx][yy]&&t.c<v[xx][yy]) q.push({xx, yy, t.c}), v[xx][yy]=t.c;
				else if(t.c+1<v[xx][yy]) q.push({xx, yy, t.c+1}), v[xx][yy]=t.c+1;
			}	
		}
		
		{
			int xx=t.x, yy=t.y; 
			xx+=dx[1], yy+=dy[1];
			if(v[xx][yy]&&xx<=n+1&&yy<=m+1&&xx&&yy)
			{
				if(!op[xx][yy-1]&&t.c<v[xx][yy]) q.push({xx, yy, t.c}), v[xx][yy]=t.c;
				else if(t.c+1<v[xx][yy]) q.push({xx, yy, t.c+1}), v[xx][yy]=t.c+1;
			}
		}
		
		{
			int xx=t.x, yy=t.y; 
			xx+=dx[2], yy+=dy[2];
			if(v[xx][yy]&&xx<=n+1&&yy<=m+1&&xx&&yy)
			{
				if(!op[xx][yy]&&t.c<v[xx][yy]) q.push({xx, yy, t.c}), v[xx][yy]=t.c;
				else if(t.c+1<v[xx][yy]) q.push({xx, yy, t.c+1}), v[xx][yy]=t.c+1;
			}
		}
		
		{
			int xx=t.x, yy=t.y; 
			xx+=dx[3], yy+=dy[3];
			if(v[xx][yy]&&xx<=n+1&&yy<=m+1&&xx&&yy)
			{
				if(op[xx-1][yy-1]&&t.c<v[xx][yy]) q.push({xx, yy, t.c}), v[xx][yy]=t.c;
				else if(t.c+1<v[xx][yy]) q.push({xx, yy, t.c+1}), v[xx][yy]=t.c+1;
		    }
		}
		
		q.pop();
	}
	if(ans==0x3f3f3f3f) puts("NO SOLUTION");
	else printf("%d\n", ans);
}
int main()
{
	int t; scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d", &n, &m);
		memset(op, 0, sizeof(op));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				char c; cin >> c;
				if(c=='/')  ; else op[i][j]=true;
			}
		}
		ans=0x3f3f3f3f; bfs();
	}
	return 0;
}