自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 21:31:03，当前版本为作者最后更新于2020-05-24 12:18:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1849 [USACO12MAR]Tractor S

题外话

这是课上的考试题，教练给了我们思路和代码让我们自己研究，那我就开始研究啦！

方法简述

01 bfs，与正常广搜及其相近。

前置芝士

queue，deque

具体方法

首先是方向移动，用两个初始化数组 $\text{stx}$ 和 $\text{sty}$ 即可。
然后是 01 bfs，用到 deque，从最开始的初始边向后走。
如果可以 push 到队首，就一直 push 到队首，反之 push 到队尾。

Code

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXM = 1000 + 5;
const int stx[4] = {0, 1, 0, -1};
const int sty[4] = {1, 0, -1, 0};

struct Node {
	int x, y;
} s;

int n, step[MAXM][MAXM];
bool map[MAXM][MAXM];
deque<Node> q;

int main () {
	scanf("%d%d%d", &n, &s.x, &s.y);
	for (int i = 1, x, y; i <= n; i++) {
		scanf("%d%d", &x, &y);
		map[x][y] = true;
	}

	memset(step, -1, sizeof(step));
	step[s.x][s.y] = 0;
	q.push_back(s);
	while (!q.empty()) {
		Node cur = q.front();
		q.pop_front();
		for (int k = 0; k < 4; k++) {
			Node nxt;
			nxt.x = cur.x + stx[k], nxt.y = cur.y + sty[k];
			if (nxt.x < 0 || nxt.x >= MAXM) continue;
			if (nxt.y < 0 || nxt.y >= MAXM) continue;
			if (step[nxt.x][nxt.y] != -1) continue;
			if (map[nxt.x][nxt.y]) {
				step[nxt.x][nxt.y] = step[cur.x][cur.y] + 1;
				q.push_back(nxt);
			}
			else {
				step[nxt.x][nxt.y] = step[cur.x][cur.y];
				q.push_front(nxt);
			}
		}
	}

	printf("%d\n", step[0][0]);
	return 0;
}

p.s. 这是我们教练给的程序 我猜他看到这个会骂我

总结与延伸

这题其实最好用的是最短路算法，这就是个最短路算法模板。
那 01 bfs 用于什么地方比较合适呢？
用于能转化为边权 $0 \text { or }1$ 的最短路问题。
所以，在 tg 组中算一个比较实用的技巧。

好的，就到这里！

参考资料

• 教练给的思路和代码
• 01 bfs 学习笔记
• 01 bfs 学习记录