保存一些没有那么难的搜索题目。

小明的游戏

是通过图论标签找到它的，结果它是一个搜索题？

怎么说呢，图论的外表，搜索的内心。

从图论的角度来想，那就是对于 \(Dijkstra\) 堆优化部分的进一步优化。由于边权 \(val\in{0,1}\) ，那么在堆中只会有两种 \(dis\) 的结点。考虑用双端队列优化这个部分。

从搜索的角度来想，如果它和国际象棋一样是交替的（也就是说它每走一步边权都是1），那么这就是当年学搜索的题目了，直接用一个队列就可以实现广搜。但问题是它的边权还有可能是0，那么我们就需要“更加高级”的队列，也就是双端队列。

两种思路实现方法一样，如果扩展的一个节点，它不比队首大，就丢到前面；反之，丢到队尾。这样就可以保持队列内部的单调性，就可以顺利完成转移。

#include<cstdio>
#include<cstring>
#include<deque>
//#define zczc
using namespace std;
const int N=510;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); }
    wh*=f;return;
}
inline bool get(){
	char w=getchar();
	while(w!='#'&&w!='@')w=getchar();
	return w=='#';
}

int m,n,fx,fy,ex,ey;
bool a[N][N];
bool entering(){
	read(m);read(n);
	if(m==0&&n==0)return false;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=get();
		}
	}
	read(fx);read(fy);read(ex);read(ey);
	fx++,fy++,ex++,ey++;
	return true;
}
int an[N][N],f[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool vis[N][N];
struct node{
	int x,y,dis;
};
deque<node>q;
inline void add(node wh){
	if(q.empty()||wh.dis<=q.front().dis)q.push_front(wh);
	else q.push_back(wh);return;
}
inline bool check(int x,int y){
	return x<1||y<1||x>m||y>n;
}
void solve(){
	memset(an,0x3f,sizeof(an));
	memset(vis,false,sizeof(vis));
	while(!q.empty())q.pop_front();
	an[fx][fy]=0;
	add((node){fx,fy,0});
	while(!q.empty()){
		node now=q.front();q.pop_front();
		int nx=now.x,ny=now.y,nd=now.dis;
		if(nx==ex&&ny==ey){
			printf("%d\n",now.dis);
			return;
		}
		if(vis[nx][ny])continue;vis[nx][ny]=true;
		for(int i=0;i<4;i++){
			int rx=nx+f[i][0],ry=ny+f[i][1];
			if(check(rx,ry))continue;
			if(an[nx][ny]+(a[nx][ny]^a[rx][ry])<an[rx][ry]){
				an[rx][ry]=an[nx][ny]+(a[nx][ny]^a[rx][ry]);
				add((node){rx,ry,an[rx][ry]});
			}
		}
	}
	return;
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	while(entering())solve();
	
	return 0;
}