[USACO19OPEN] Bucket Brigade B题解

· · 题解

思路：

这道题一看只有一块石头，这一眼看上去就可以不用深搜了么？

按照样例解释一下：

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

这是给我们的图。

最短的路程显然就是

..........
..........
..........
..B.......
..C.......
..C..R....
..C.......
..C.......
..CCCL....
..........

但是如果他在第 6 行第 3 列放一块大石头呢，我们仍然可以按照同样的方法计算。

..........
..........
..........
..BCCC....
.....C....
..R..C....
.....C....
.....C....
.....L....
..........

我们可以根据只有一个石头的特点直接计算出答案，结果也就是 \left\vert Bx-Lx\right\vert+\left\vert By-Ly\right\vert-1。

但是我们只能获得 70 分的好成绩，因为我们忽略了一个情况。

..........
..........
....L.....
..........
..........
....R.....
..........
..........
....B.....
..........

这样的话我们这块石头也就挡住了我们的最简单的路线，所以我们可以往两边放两头奶牛凸出来。

..........
..........
...CL.....
...C......
...C......
...CR.....
...C......
...C......
...CB.....
..........

这样我们只需要判断一下是不是这三个坐标都连在一起，答案也就是原来的再加上 2。

可惜我们低估了数据的强度，这样还是只能拿到 80 分的成绩。

..........
..........
....L.....
..........
..........
....B.....
..........
..........
....R.....
..........

对于这种情况，我们发现确实是连在了一起，但是这个起点与终点的路上完全不需要躲避大石头，就只需要判断一下是不是这条路线包含这个大石头。

代码：

//
// Created by 55062 on 2024/1/14.
//
#include<bits/stdc++.h>
using namespace std;
typedef long ll;
char a[20][20];
ll Bx,By,Lx,Ly,Rx,Ry;
int main(){
    for(int i=1;i<=10;i++)
        for(int j=1;j<=10;j++){
            cin>>a[i][j];
            if(a[i][j]=='B') Bx=i,By=j;
            if(a[i][j]=='L') Lx=i,Ly=j;
            if(a[i][j]=='R') Rx=i,Ry=j;
        }
    if(Bx==Lx&&Lx==Rx&&(By>=Ry&&Ly<=Ry||Ly>=Ry&&By<=Ry)||By==Ly&&Ly==Ry&&(Bx>=Rx&&Lx<=Rx||Lx>=Rx&&Bx<=Rx)) cout<<abs(Bx-Lx)+abs(By-Ly)+1;
    else cout<<abs(Bx-Lx)+abs(By-Ly)-1;
    return 0;
}