题解 P1849 【[USACO12MAR]Tractor S】

· · 题解

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 组中算一个比较实用的技巧。

好的，就到这里！

参考资料