双端队列bfs rt

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<deque>
#define ll long long
#define rep(i,a,n) for(register int i=a;i<=n;++i)
#define dwn(i,n,a) for(register int i=n;i>=a;--i)
using namespace std;
ll n,m,map[1005][1005],cst[1005][1005],x_1,x_2,y_1,y_2;
bool book[1005][1005];
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct node
{
	ll x,y;
};
deque<node> q;
inline ll read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
void write(ll x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar('0'+x%10);
}
int main()
{
	while(1)
	{
		n=read(),m=read();
		if((!n)&&(!m))break;
		char ch;
		rep(i,0,n-1)
		{
			rep(j,0,m-1)
			{
				ch=getchar();
				if(ch=='#')map[i][j]=1;
				else map[i][j]=0;
			}
			getchar();
		}
		rep(i,0,n-1)
			rep(j,0,m-1)cst[i][j]=1e9;
		memset(book,false,sizeof(book));
		while(!q.empty())q.pop_front();
		x_1=read(),y_1=read(),x_2=read(),y_2=read();
		node d;
		d.x=x_1,d.y=y_1;
		q.push_back(d);
		cst[x_1][y_1]=0;
		while(!q.empty())
		{
			ll x=q.front().x,y=q.front().y;
			q.pop_front();
			if(book[x][y])continue;
			book[x][y]=true;
			rep(i,0,3)
			{
				ll nx=x+dx[i],ny=y+dy[i];
				if(nx<0||nx>n-1||ny<0||ny>m-1)continue;
				if(cst[x][y]+(map[x][y]^map[nx][ny])>cst[nx][ny])continue;
				cst[nx][ny]=cst[x][y]+(map[x][y]^map[nx][ny]);
				d.x=nx,d.y=ny;
				if(map[x][y]^map[nx][ny])q.push_back(d);
				else q.push_front(d);
			}
		}
		write(cst[x_2][y_2]);
		putchar('\n');
	}
	return 0;
}