双端队列代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,d[505][505];
char s[505][505];
struct node{
	int x,y,sum;
};
deque<node>q;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int a1,b1,a2,b2;
int main(){
	ios::sync_with_stdio(false);
	while(1){
		cin>>n>>m;
		if(n==0&&m==0) break;
		for(int i=1;i<=n;i++) cin>>(s[i]+1);
		cin>>a1>>b2>>a2>>b2;
		a1++,b1++,a2++,b2++;
		while(!q.empty()) q.pop_back();
		memset(d,0x3f,sizeof(d));
		q.push_back(node{a1,b1,0});
		d[a1][b1]=0;
		while(!q.empty()){
			node x=q.front();
			q.pop_front();
			if(x.x==a2&&x.y==b2){
				cout<<x.sum<<endl;
				break;
			}
			for(int i=0;i<4;i++){
				int tx=x.x+dx[i];
				int ty=x.y+dy[i];
				if(tx<1||ty<1||tx>n||ty>m) continue;
				if(s[x.x][x.y]==s[tx][ty]){
					if(x.sum>=d[tx][ty]) continue;
					else{
						d[tx][ty]=x.sum;
						q.push_front(node{tx,ty,x.sum});
					}
				}
				else{
					if(x.sum+1>=d[tx][ty]) continue;
					else{
						d[tx][ty]=x.sum+1;
						q.push_back(node{tx,ty,x.sum+1});
					}
				}
			}
		}
	}
	return 0;
}