题解：CF253C Text Editor

说明提示

翻译坑人！这道题在 CF 上是要文件操作的，见下图。

做法

见到这道题我们可以发现可以用题目中给出的条件建一张图，而这道题中所有边的边权均为 $1$，因此可以使用 BFS。

BFS 广度优先搜索是使用队列（queue，先进先出）来实现，整个过程也可以看做一个倒立的树形：

1. 把根节点放到队列的末尾。
2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾 (不需要排序，因为默认每次增加权重相同)。并把这个元素记为它下一级元素的前驱。
3. 找到所要找的元素时结束程序。
4. 如果遍历整个树还没有找到，结束程序。

代码

#include<bits/stdc++.h>
using namespace std;
int n, a[100 + 5], bx, by, ex, ey;
bool vis[100 + 5][100000 + 5];
int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	queue<tuple<int, int, int>>q;
	cin >> bx >> by >> ex >> ey;
	q.emplace(bx, by, 0);
	while (!q.empty()) {
		tuple<int, int, int>now = q.front(); q.pop();
		int x = get<0>(now), y = get<1>(now), d = get<2>(now);
		if (vis[x][y]) continue;
		vis[x][y] = 1;
		if (x == ex && y == ey) {
			cout << d << endl;
			return 0;
		}
		if (y > 1) q.emplace(x, y - 1, d + 1);
		if (y <= a[x]) q.emplace(x, y + 1, d + 1);
		if (x > 1 && a[x - 1] + 1 >= y) q.emplace(x - 1, y, d + 1);
		if (x < n && a[x + 1] + 1 >= y) q.emplace(x + 1, y, d + 1);
		if (x > 1 && a[x - 1] + 1 < y) q.emplace(x - 1, a[x - 1] + 1, d + 1);
		if (x < n && a[x + 1] + 1 < y) q.emplace(x + 1, a[x + 1] + 1, d + 1);
	}
}

AC 记录