01BFS

学不会的BFS，神仙建图

干啥的

用来解决：边权值为 或 ，或者能够转化为这种边权值的最短路问题

在 bfs 的基础上做如下改动：

1. 用 deque 取代 queue
2. 边权为 时，从双端队列的前端插入；边权为 时，从双端队列的后端插入。

悟悟悟

例1

Eva.oj 0005

给一个 迷宫， . 代表道路，# 代表墙 ，求从 到 所需要拐弯的最少次数。

解1

技巧：拆点。把每一个点拆成水平方向和垂直方向的两个点。

依次给拆开的点编号。先存水平方向的，再存垂直方向的，水平点之间的边和垂直点之间的边边权为 ，再在垂直点和水平点之间连一条边，边权为 。

水平方向的点用 ida(int x, int y) 计算编号，依次从 到 。

垂直方向的点用 idb(int x, int y) 计算编号，依次从 到 。

pair(int a, int b) ：a 代表点的编号，b 代表边权 。

再连接同一个点的水平点和垂直点，边权为 。

e[N * N * 2] 邻接表。

dis[N * N * 2] 存放距离。

#include<bits/stdc++.h>
#define N 1007 
#define mp make_pair
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define pf push_front 
using namespace std;

int n, m, dis[N * N * 2];

deque<int> dq;

int ida(int x, int y) {return (x - 1) * m + y;}

int idb(int x, int y) {return (x - 1) * m + y + n * m;}

bool ty[N][N];

inline bool valid(int x, int y) {
	return x > 0 && x <= n && y > 0 && y <= m && ty[x][y];
}

vector<pii> e[N * N * 2];

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			char c = getchar();
			while (c != '.' && c != '#') c = getchar();
			ty[i][j] = (c == '.');
		}
	for (int x = 1; x <= n; ++x)
		for (int y = 1; y <= m; ++y) {
			dis[ida(x, y)] = dis[idb(x, y)] = 1000000000;
			if (ty[x][y]) {
				for (int k = 0, tx, ty; k < 2; ++k) {
					tx = x + dx[k]; ty = y + dy[k];
					if (valid(tx, ty)) e[ida(x, y)].pb(mp(ida(tx, ty), 0));
				}
				for (int k = 2, tx, ty; k < 4; ++k) {
					tx = x + dx[k]; ty = y + dy[k];
					if (valid(tx, ty)) e[idb(x, y)].pb(mp(idb(tx, ty), 0));
				}
				e[ida(x, y)].pb(mp(idb(x, y), 1));
				e[idb(x, y)].pb(mp(ida(x, y), 1)); 
			}
		}
	dis[1] = dis[n * m + 1] = 0;
	dq.pb(1); dq.pb(n * m + 1);
	while(!dq.empty()){
		int t = dq.front();
		dq.pop_front();
		for(auto i : e[t]){
			if(dis[i.fr] > dis[t] + i.sc) {
				dis[i.fr] = dis[t] + i.sc;
				i.sc ? dq.pb(i.fr) : dq.pf(i.fr);
			}
		}
	}
	int ans = min(dis[n * m], dis[n * m * 2]);
	if(ans == 1000000000) printf("Impossible!!!!");
	else printf("%d", ans);
	return 0;
} 

练练练

例1

Wizard in Maze

https://atcoder.jp/contests/abc176/tasks/abc176_d

给一个无向图，. 代表道路 # 代表墙。有两种移动方法：

1. 向上下左右走，代价为
2. 使用一次魔法，可以任意移动到以该点为中心的 5*5 的矩阵中的任意一点，代价为

给定起点和终点，问从起点运动到终点所需代价最小为多少。

解1

我们先将起点放入队列中，依次扫描跟起点相连的点（上下左右，和 5*5 矩阵里的点），当 dis 能被更新时，就更新。更新以后放入队列。

这里为什么不开 vis 呢？？

因为有可能出现以下情况：队列里的两个点 都与点 相连，从 到 的代价为 ，而从 到 的代价为 。如果用 vis 打标记的话，它最终会从 点连边到 ，而不是

#include<bits/stdc++.h>
#define N 1007
using namespace std;

int n, m, bex, bey, fix, fiy, dis[N][N];

bool ty[N][N];

deque<pair<int, int> > q;

inline bool valid(int x, int y) {
	return x > 0 && x <= n && y > 0 && y <= m && ty[x][y];
}

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

int main() {
	cin >> n >> m >> bex >> bey >> fix >> fiy;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			char c = getchar();
			while (c != '.' && c != '#') c = getchar();
			ty[i][j] = (c == '.');
			dis[i][j] = 1000000000;
		}
	if(!valid(bex, bey)){
		cout << "-1" << endl;
		return 0;
	}
	dis[bex][bey] = 0;
	q.push_front(make_pair(bex, bey));
	while(!q.empty()){
		pair<int, int> t = q.front();
		q.pop_front();
		for(int i = 0; i < 4; ++i){
			int tx = t.first + dx[i];
			int ty = t.second + dy[i];
			if(valid(tx, ty) && dis[tx][ty] > dis[t.first][t.second]) {
				dis[tx][ty] = dis[t.first][t.second];
				q.push_front(make_pair(tx, ty));
			}
		}
		for(int i = -2; i <= 2; ++i){
			for(int j = -2; j <= 2; ++j){
				int tx = t.first + i;
				int ty = t.second + j;
				if(valid(tx, ty) && dis[tx][ty] > dis[t.first][t.second] + 1){
					dis[tx][ty] = dis[t.first][t.second] + 1;
					q.push_back(make_pair(tx, ty));
				}
			}
		}
	}
	if(dis[fix][fiy] == 1000000000) cout << "-1" << endl;
	else cout << dis[fix][fiy] << endl;
	return 0;
}

例2

https://codeforces.com/problemset/problem/1046/D