01BFS

• 走的时候有两种走法，维护双端队列，一种走法代价是0，进入队首，另一种走法代价是？，放入队尾

题意

• 给定地图，给定n次起点和终点，每次输出最短时间
• 特别的，一个点可以向八个方向走，且向其中一个方向走不耗时，其他方向耗时为1

思路

• 与maze那道题类似，都需要处理队列中时间最短的，但本题不会出现跨越多种不同步长的情况，所以可以不用优先队列，使用一个双端队列来维护即可，对于每一个点尝试移动的时候，不耗时的方向直接放到队首，其余方向放到队尾，仍然保证了队列中耗时差不会超过1秒

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int mp[1020][1020];
int vis[1020][1020];
int dir[8][2]={-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};
int bfs(int sx,int sy,int ex,int ey){
	if(sx==ex&&sy==ey)return 0;
	deque<pair<int,int>>q;
	q.push_back({sx*(m+1)+sy,0});
	while(q.size()){
		int x=q.front().first/(m+1);
		int y=q.front().first%(m+1);
		int stp=q.front().second;
		q.pop_front();
		if(vis[x][y])continue;
		if(x==ex&&y==ey)return stp;
		vis[x][y]=1;
		for(int i=0;i<8;i++){
			int tx=x+dir[i][0];
			int ty=y+dir[i][1];
			if(tx<1||ty<1||tx>n||ty>m||vis[tx][ty]){continue;}
			if(i==mp[x][y]) q.push_front({tx*(m+1)+ty,stp});
			else q.push_back({tx*(m+1)+ty,stp+1});
		}
	}
	return -1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%1d",&mp[i][j]);
		}
	}
	int t;
	scanf("%d",&t);
	int sx,sy,ex,ey;
	while(t--){
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		memset(vis,0, sizeof(vis));
		printf("%d\n",bfs(sx,sy,ex,ey));
	}
	return 0;
}

PS

• 1起点的坐标转化为一个数的时候是x*(m+1)+y,调半天，烦死