“最小花费”，我们可以使用bfs来解决。但本题不是普通的bfs，每一个点有两种状态。bfs要求队列中的元素必须有序来实现最优性，所以本题不能简单粗暴地使用普通队列——那会导致队列失去有序。

本题需要使用双端队列，当当前点与下一个点相同时我们就将其加到队头，否则加入队尾，这样就能保证有序了。

#include<bits/stdc++.h>
using namespace std;
const int N=505,d[4][2]={1,0,-1,0,0,-1,0,1};
int n,m,sx,sy,tx,ty,ans[N][N];
char c[N][N];
struct node{
	int x,y;
};
deque<node> dq;
int bfs(){
	memset(ans,0x3f,sizeof(ans));
	ans[sx][sy]=0;
	dq.push_back({sx,sy});
	while(!dq.empty()){
		int x=dq.front().x,y=dq.front().y;
		dq.pop_front();
		for(int i=0;i<4;i++){
			int xx=x+d[i][0],yy=y+d[i][1];
			if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&ans[xx][yy]>ans[x][y]+(c[x][y]!=c[xx][yy])){
				ans[xx][yy]=ans[x][y]+(c[x][y]!=c[xx][yy]);
				if(c[x][y]==c[xx][yy])
					dq.push_front({xx,yy});
				else
					dq.push_back({xx,yy});
			}
		}
	}
	return ans[tx][ty];
}
int main(){
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0)
			return 0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>c[i][j];
		scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
		sx++,sy++,tx++,ty++; // 注意到下标是从0开始的，程序是中以1为边界的所以把坐标全部加1
		printf("%d\n",bfs());
	}
}

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t,d[501][501],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
char c[501][501];
deque<pair<int,int>>q;
int main()
{
    cin>>n>>m;
    int x1,y1,x2,y2;
    while(n)
    {
        for(int i=0;i<n;i+=1)cin>>c[i];
        memset(d,63,sizeof(d));
        cin>>x1>>y1>>x2>>y2;
        d[x1][y1]=0;
        q.push_front({x1,y1});
        while(!q.empty())
        {
            int x=q.front().first;
            int y=q.front().second;
            q.pop_front();
            for(int i=0;i<=3;i+=1)
            {
                int _x=x+dx[i];
                int _y=y+dy[i];
                if(_x>=0&&_x<n&&_y>=0&&_y<m&&d[_x][_y]>d[x][y]+(c[x][y]!=c[_x][_y]))
                {
                    d[_x][_y]=d[x][y]+(c[x][y]!=c[_x][_y]);
                    if(c[x][y]==c[_x][_y])q.push_front({_x,_y});
                    q.push_back({_x,_y});
                }
            }
        }
        cout<<d[x2][y2]<<'\n';
        cin>>n>>m;
    }
}