"蔚来杯"2022牛客暑期多校训练营3 - J. Journey题解($0\mathrm{/}10/1$BFS)

Journey

原题指路:https://ac.nowcoder.com/acm/contest/33188/J

题意

某城市有$nn$个十字路口.某人每次有两种行进方式:①直走、左转或原地转身:要等一个红灯;②右转:无需等红灯.求他从起始的马路到达他想到的马路最少需等多少红灯.

第一行输入整数$n(2\le n\le 5\mathrm{e}5)n\backslash \; \backslash \; (2\backslash leq\; n\backslash leq\; 5\backslash mathrm\{e\}5)$,表示该城市的十字路口数.接下来$nn$行每行输入四个相异的整数$c_{i,1},c_{i,2},c_{i,3},c_{i,4}(0\le c_{i,j}\le n)c\_\{i,1\},c\_\{i,2\},c\_\{i,3\},c\_\{i,4\}\backslash \; \backslash \; (0\backslash leq\; c\_\{i,j\}\backslash leq\; n)$,分别表示第$ii$个十字路口的四条马路的起点,其中$c_{i,j}=0c\_\{i,j\}=0$的马路某人不会经过.马路以逆时针排列,换句话说,设某人当前在马路,若他想前往马路,因为这是右转,所以他无需等红灯;否则,若他想前往其他马路,则他需等红灯.数据保证地图中不存在重边和自环,且每条马路都是双向边.最后一行输入四个整数$s_1,s_2,t_1,t_2(1\le s_1,s_2,t_1,t_2\le n)s\_1,s\_2,t\_1,t\_2\backslash \; \backslash \; (1\backslash leq\; s\_1,s\_2,t\_1,t\_2\backslash leq\; n)$,表示初始时某人在马路,他想到达马路,数据保证起点和终点的马路在上述地图中.

输出一个整数,表示他从起点到终点最少需等多少红灯.

Input

4
3 4 0 0
0 0 4 3
2 1 0 0
2 0 0 1
4 2 4 1

Output

1

样例解释

题面表述不清,大意为某人有四个朝向,在他所在的十字路口,右转则无需等红灯,其余情况都需等一个红灯.输入的最后一行描述他的起点马路和朝向、终点马路和朝向.

对输入描述的地图的解释:

第一行$44$,表示有$44$个十字路口,可理解为有$44$个城市.

第二行$34003\backslash \; 4\backslash \; 0\backslash \; 0$,表示城市$11$与城市$3,43,4$间有马路相连,且城市$1,3,41,3,4$逆时针排列.

第三行$00430\backslash \; 0\backslash \; 4\backslash \; 3$,表示城市$22$与城市$4,34,3$间有马路相连,且城市$2,4,32,4,3$逆时针排列.

第四行$21002\backslash \; 1\backslash \; 0\backslash \; 0$,表示城市$33$与城市$2,12,1$间有马路相连,且城市$3,2,13,2,1$逆时针排列.

第五行$20012\backslash \; 0\backslash \; 0\backslash \; 1$,表示城市$44$与城市$2,12,1$间有马路相连,且城市$4,2,14,2,1$逆时针排列.

对朝向的解释:

某人初始时在马路,表示他在城市$44$与$22$间的边上,且朝向城市$22$,如上图蓝色箭头所示.

某人想到马路,表示他想到城市$44$与$11$间的边上,且朝向城市$11$,如上图红色箭头所示.

对答案的解释:

某人当前在马路,他直走到城市$22$,因为马路不是十字路口所以无需等红灯.

现他在城市$22$处,朝向依旧是$4\to 24\backslash rightarrow\; 2$.而城市$22$的输入行$00430\backslash \; 0\backslash \; 4\backslash \; 3$中城市$44$在下标为$33$的位置,则朝向$4\to 24\backslash rightarrow\; 2$即$pos=3pos=3$.

​ 因$pos\mathrm{\%}4+1=4pos\backslash \%4+1=4$,则城市$22$的输入行中下标为$44$的城市$33$即在城市$22$处右转能到达的城市,无需等红灯;

​ 到达其余城市(本行中无)需等红灯.

现他在城市$22$的十字路口处右转,直走到达城市$33$,过程中无需等红灯.

现他在城市$33$处,朝向$2\to 32\backslash rightarrow\; 3$.而城市$33$的输入行$21002\backslash \; 1\backslash \; 0\backslash \; 0$中城市$22$在下标为$11$的位置,则朝向$2\to 32\backslash rightarrow\; 3$即$pos=1pos=1$.

​ 因$pos\mathrm{\%}+1=2pos\backslash \%+1=2$,则城市$33$的输入行中下标为$22$的城市$11$即在城市$33$​处右转能到达的城市,无需等红灯;

​ 到达其余城市(本行中无)需等红灯.

现他在城市$33$的十字路口处右转,直走到达城市$11$,过程中无需等红灯.

现他在城市$11$处,朝向$3\to 13\backslash rightarrow\; 1$,而城市$11$的输入行$34003\backslash \; 4\backslash \; 0\backslash \; 0$中城市$33$在下标$11$的位置,则朝向$3\to 13\backslash rightarrow\; 1$即$pos=1pos=1$.

​ 因$pos\mathrm{\%}+1=2pos\backslash \%+1=2$,则城市$11$的输入行中下标为$22$的城市$44$即在城市$11$​处右转能到达的城市,无需等红灯;

​ 到达其余城市(本行中无)需等红灯.

现他在城市$11$的十字路口处右转,直走到达城市$44$,过程中无需等红灯.

现他在马路上,但朝向为$1\to 41\backslash rightarrow\; 4$,而他的目标朝向是$4\to 14\backslash rightarrow\; 1$,故他需等一次红灯完成转向.

可以证明,等一次红灯是最优解.

思路

将城市视为点,城市间的马路视为边,则能通过直走、左转、右转到达的城市间有边相连.右转无需等红灯,则当前城市到右转到达的城市间有边权为$00$的边;其他行进方式需等一个红灯,则当前城市到其他行进方式到达的城市间有边权为$11$的边.边权只有$00$和$11$,考虑$0\mathrm{/}10/1$BFS.注意这样转化后无需将整个图建出来,只需根据输入的矩阵$c[][]c[][]$即可得到每个点能以什么行进方式到达哪些点.总体思路:通过边权为$00$的边能到达的点(右转能到达的城市)插入到双端队列的队首,花费不变;其他城市插入到队尾,花费$+1+1$.BFS扩展时优先扩展通过边权为$00$的边能到达的点,显然这是最优的.

用一个三元组$(cur,pre,cost)(cur,pre,cost)$表示从城市$prepre$到城市$curcur$的花费为$costcost$,用一个全局的$ansans$记录等红灯数的最小值(后面会看见它可能会被多次更新),$ansans$初始化为ll的最大值$INFFINFF$.注意每取出一个新的队首都需更新当前的朝向$pospos$,即找到一个$s\mathrm{.}t\mathrm{.}c[cur][pos]=pre\backslash \; s.t.\backslash \; c[cur][pos]=pre$的$pospos$.

①每次取出队首元素$tmptmp$,若$tmptmp$的$cost\ge anscost\backslash geq\; ans$,因策略是优先扩展通过边权为$00$的边能到达的点,则出现了第一个不小于之前更新过的$ansans$的$costcost$时,后面的$costcost$只能不变或增加,显然$ansans$是等红灯数的最小值,直接返回.$ansans$初始化为ll的最大值$INFFINFF$.

②若$(cur,pre)=(t_2,t_1)(cur,pre)=(t\_2,t\_1)$,即走到了目标马路且朝向正确,因策略是优先扩展通过边权为$00$的边能到达的点,则第一次到达时一定是最优解,直接返回当前的$costcost$.

③若$(cur,pre)=(t_1,t_2)(cur,pre)=(t\_1,t\_2)$,即走到了目标马路但朝向相反,注意此时不能确定$(cost+1)(cost+1)$是否是最优解,因为可能存在另一条一直右转的路径使得最后到达了目标马路且朝向正确,故先用$ansans$记录当前的$(cost+1)(cost+1)$,并继续扩展下一个队首元素.

④判重,注意不能只开一个一维的$vis[]vis[]$表示每个点是否被遍历过,因为从不同的方向到达相同的点花费可能不同,故应开一个二维的$vis[][]vis[][]$,其中$vis[u][pos]vis[u][pos]$表示表示从$pospos$方向到点$uu$是否被遍历过.

⑤若队列空后都未返回,则检查$ansans$是否是$INFFINFF$,若是则无解,返回$-1-1$;否则返回$ansans$.

代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<complex>
#include<array>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int, int, int> tiii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef queue<pii> qii;
typedef complex<double> cp;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl '\n'
#define npt nullptr
#define so sizeof
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define hashset_finetune(p) (p).reserve(1024); (p).max_load_factor(0.25);  // 哈希表防卡
const double eps = 1e-7;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int dx[4] = { 0,-1,0,1 }, dy[4] = { -1,0,1,0 };
// ----------------------------------------------------------------
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }  // 注意要不要改成ll
int lcm(int a, int b) { return a * b / gcd(a, b); }  // 注意要不要改成ll
int lowbit(int x) { return x & (-x); }
int cmp(double a, double b) {
	if (fabs(a - b) < eps) return 0;
	else if (a > b) return 1;
	else return -1;
}
int sgn(double x) {
	if (fabs(x) < eps) return 0;
	else if (x > 0) return 1;
	else return -1;
}

template<typename T>
void read(T& x) {
	x = 0;
	T sgn = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') sgn = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch & 15);
		ch = getchar();
	}
	x *= sgn;
}

template<typename T>
void write(T x) {
	if (x < 0) {
		putchar('-');
		x *= -1;
	}
	if (x < 10) putchar(x + 48);
	else write(x / 10), putchar(x % 10 + 48);
}

ll qpow(ll a, ll k, ll MOD) {
	ll res = 1;
	while (k) {
		if (k & 1) res = res * a % MOD;
		k >>= 1;
		a = a * a % MOD;
	}
	return res;
}
// ----------------------------------------------------------------

typedef tuple<int, int, ll> tiil;
const int MAXN = 5e5 + 5;
int n;
int c[MAXN][5];
int s1, s2, t1, t2;
bool vis[MAXN][5];  // vis[u][pos]表示从pos方向到点u是否被遍历过

ll bfs(int s1, int s2) {
	ll ans = INFF;
	deque<tiil> que;
	que.push_back({ s2, s1, 0 });  /// cur,pre,cost

	while (que.size()) {
		auto tmp = que.front(); que.pop_front();
		int cur, pre;
		ll cost;
		tie(cur, pre, cost) = tmp;
		if (!cur) continue;  // 走到了不存在的节点
		if (cost >= ans) return ans;  // 当前的花费不是最优解,返回之前找到的最优解
		if (cur == t2 && pre == t1) return cost;  // 能直接走到的一定是最优解
		if (cur == t1 && pre == t2) {  // 走到边上但还要转向的未必是最优解,注意不能直接return cost + 1;
			ans = cost + 1;
			continue;
		}

		int pos;  // 当前朝向
		for (int i = 1; i <= 4; i++) {
			if (c[cur][i] == pre) {
				pos = i;
				break;
			}
		}
			
		if (vis[cur][pos]) continue;  // 走过该点的该方向
		vis[cur][pos] = true;

		ll res = cost;
		que.push_front({ c[cur][pos % 4 + 1], cur, res });  // 右转无需花费,插到队首
		for (int i = 1; i <= 4; i++)  // 其他方向需要花费,插到队尾
			if (i != pos) que.push_back({ c[cur][i % 4 + 1], cur, res + 1 });
	}

	return ans == INFF ? -1 : ans;
}

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> c[i][1] >> c[i][2] >> c[i][3] >> c[i][4];
	cin >> s1 >> s2 >> t1 >> t2;

	cout << bfs(s1, s2);
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}