代码：

#include<bits/stdc++.h>
using namespace std;
const int M=4e6+5000;
char e[1050][1050];
bool vis[M>>2];
int t,n,m,cnt,sum;
struct edge
{
    int nxt,to,val;
}ed[M];
int fir[M>>2],dist[M>>2];
void add(int u,int v,int w)
{
    ed[++cnt].nxt=fir[u];
    ed[cnt].to=v;
    ed[cnt].val=w;
    fir[u]=cnt;
}
inline int read()
{
	int x=0,y=1;//x是什么，y是正负 
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*y;
}
void _01BFS(int x)
{
    for(int i=1;i<=sum;i++)
    {
        dist[i]=INT_MAX;
        vis[i]=false;
    }
    deque<int> q;
    dist[x]=0;
    q.push_back(x);
    vis[x]=true;
    while(q.size())
    {
        int p=q.front();
        q.pop_front();
        vis[p]=false;
        for(int i=fir[p];i;i=ed[i].nxt)
        {
            int v=ed[i].to;
            int d=dist[p]+ed[i].val;
            if(dist[v]>d)
            {
                dist[v]=d;
                if(!vis[v])
                {
                    vis[v]=true;
                    if(ed[i].val==0) q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
}
int main()
{
    char c;
    t=read();
    while(t--)
    {
        n=read(),m=read();
        sum=n*m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                while(c<'a'||c>'z') c=getchar();
                e[i][j]=c;
                c='\0';
            }
        for(int i=1;i<=n;i++)//建图
            for(int j=1;j<=m;j++)
            {
                int pos=(i-1)*m+j;
                if(i+1<=n) add(pos,pos+m,e[i][j]==e[i+1][j]?0:1);
                if(i-1>=1) add(pos,pos-m,e[i][j]==e[i-1][j]?0:1);
                if(j+1<=m) add(pos,pos+1,e[i][j]==e[i][j+1]?0:1);
                if(j-1>=1) add(pos,pos-1,e[i][j]==e[i][j-1]?0:1);
            }
        
        _01BFS(1);
        printf("%d\n",dist[sum]);
        // for(int i=1;i<=cnt;i++)
        // {
        //     ed[i].to=0;
        //     ed[i].val=0;
        //     ed[i].nxt=0;
        // }
        memset(fir,0,sizeof(fir));
        // memset(e,'\0',sizeof(e));  
        cnt=0;
    }
    return 0;
}