题目链接

#include <bits/stdc++.h>
using namespace std;
char a[1001][1001];
int T,n,m,qx[10]={-1,1,1,-1},qy[10]={1,1,-1,-1};
int f[1001][1001][6],vis[1001][1001],d[1001][1001];
void bfs()
{
	memset(vis,0,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	deque< pair<int,int> >q;
	q.push_front(make_pair(1,1));
	d[1][1]=0;
	while(q.size())
	{
		pair<int,int> u=q.front();
		q.pop_front();
		int x=u.first,y=u.second;
		vis[x][y]=1;		
		for(int i=0;i<4;i++)
		{
			int nx=x+qx[i];
			int ny=y+qy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0)
			{
//				if(f[x][y][i])
//				{
//					if(d[x][y]<d[nx][ny])
//					{
//						d[nx][ny]=d[x][y];
//						q.push_front(make_pair(nx,ny));
//					}				
//				}
//				else
//				{
//					if(d[x][y]+1<d[nx][ny])
//					{
//						d[nx][ny]=d[x][y]+1;
//						q.push_back(make_pair(nx,ny));
//					}						
//				}
                int dis=d[x][y]+f[x][y][i];
                if(dis<d[nx][ny])
                {
                	d[nx][ny]=dis;
                	q.push_front(make_pair(nx,ny));
				}
			}
		}
	}
	return;
}
int main()
{
	cin>>T;
	for(int k=1;k<=T;k++)
    {
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				scanf("%c",&a[i][j]);
				if(a[i][j]=='/')
				{
					f[i+1][j][0]=0;
					f[i][j+1][2]=0;
					f[i][j][1]=1;
					f[i+1][j+1][3]=1;
				}
				else
				{
					f[i+1][j][0]=1;
					f[i][j+1][2]=1;
					f[i][j][1]=0;
					f[i+1][j+1][3]=0;					
				}
			}
		}
		n++,m++;
		bfs();
		if(vis[n][m])
		cout<<d[n][m]<<endl;
		else
		cout<<"NO SOLUTION"<<endl;	
//		memset(a,'0',sizeof(a));
	}
}