菜炸了，改不出来。

code：

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int maxn=510;
int n;
char a[maxn][maxn];
vector<pii> edge[maxn][maxn];
vector<int> val[maxn][maxn];
void add(int ux,int uy,int vx,int vy,int w)
{
	edge[ux][uy].push_back(mp(vx,vy));
	val[ux][uy].push_back(w);
}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool inbound(int x,int y)
{
	return x>0&&y>0&&x<=n&&y<=n;
}
int lp[maxn][maxn],rp[maxn][maxn],up[maxn][maxn],down[maxn][maxn];
int dis[maxn][maxn];
bool vis[maxn][maxn];
struct node
{
	int x,y,w;
    bool operator<(const node &x) const
	{
        return w>x.w;
	}
};
void dijkstra()
{
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=n+1;j++)
			dis[i][j]=1e9;
	dis[1][1]=0;
	memset(vis,0,sizeof(vis));
	priority_queue<node> q;
	q.push({1,1,0});
	while(!q.empty())
	{
		int ux=q.top().x,uy=q.top().y;
		q.pop();
		if(vis[ux][uy]) continue;
		vis[ux][uy]=1;
		for(int j=0;j<edge[ux][uy].size();j++)
		{
			int vx=edge[ux][uy][j].fi,vy=edge[ux][uy][j].se;
			int w=val[ux][uy][j];
            if(dis[vx][vy]>dis[ux][uy]+w)
			{
                dis[vx][vy]=dis[ux][uy]+w;
                node t;
                t.x=vx,t.y=vy,t.w=dis[vx][vy];
                if(!vis[vx][vy])
                	q.push(t);
            }
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		memset(lp,0,sizeof(lp));
		memset(rp,0,sizeof(rp));
		memset(up,0,sizeof(up));
		memset(down,0,sizeof(down));
		cin>>n;
		memset(a,'\0',sizeof(a));
		for(int i=0;i<=n+1;i++)
			for(int j=0;j<=n+1;j++)
				edge[i][j].clear(),val[i][j].clear();
		for(int i=1;i<=n;i++) cin>>a[i]+1;
		if(a[1][1]!='.'||a[n][n]!='.') return 0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				for(int k=0;k<4;k++)
				{
					int nx=i+dx[k],ny=j+dy[k];
					if(!inbound(nx,ny)) continue;
					if(a[i][j]==a[nx][ny]&&a[i][j]=='.') add(i,j,nx,ny,0),add(nx,ny,i,j,0);
				}
		for(int i=1;i<=n;i++)
		{
			for(int j=n;j>=1;j--)
			{
				if(a[i][j+1]!='.'&&a[i][j+1]!='*') rp[i][j]=j+1;
				else rp[i][j]=rp[i][j+1];
			}
			for(int j=1;j<=n;j++)
			{
				if(a[i][j-1]!='.'&&a[i][j-1]!='*') lp[i][j]=j-1;
				else lp[i][j]=lp[i][j-1];
			}			
		}
		for(int j=1;j<=n;j++)
		{
			for(int i=1;i<=n;i++)
			{
				if(a[i-1][j]!='.'&&a[i-1][j]!='*') up[i][j]=i-1;
				else up[i][j]=up[i-1][j];
			}
			for(int i=n;i>=1;i--)
			{
				if(a[i+1][j]!='.'&&a[i+1][j]!='*') down[i][j]=i+1;
				else down[i][j]=down[i+1][j];
			}			
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(a[i][j]=='*'||a[i][j]=='#') continue;
				add(i,j,i,lp[i][j],1);
				add(i,j,i,rp[i][j],1);
				add(i,j,up[i][j],j,1);
				add(i,j,down[i][j],j,1);
				//cout<<i<<" "<<j<<" : "<<i<<" "<<rp[i][j]<<" "<<i<<" "<<lp[i][j]<<" "<<up[i][j]<<" "<<j<<" "<<down[i][j]<<" "<<j<<endl;
			}
		}
		for(int i=0;i<=n+1;i++)
		{
			for(int j=0;j<=n+1;j++)
			{
				if(a[i][j]=='.'||a[i][j]=='*') continue;
				for(int k=0;k<4;k++)
				{
					int nx=i+dx[k],ny=j+dy[k];
					if(!inbound(nx,ny)) continue;
					if(a[nx][ny]=='*'||a[nx][ny]=='#') continue;
					add(i,j,nx,ny,1);
				}
			}
		}
		dijkstra();
//		for(int i=1;i<=n;i++)
//		{
//			for(int j=1;j<=n;j++)
//			{
//				if(dis[i][j]<1e9)
//					cout<<dis[i][j]<<" ";
//				else cout<<"? ";
//			}
//			cout<<endl;
//		}
		if(dis[n][n]<1e6)
			cout<<dis[n][n]<<endl;
		else
			cout<<-1<<endl;
	}
	return 0;
}
/*
1
5
...*.
*##*.
#..*.
#*###
.....
*/