自动搬运

查看原文

来自洛谷，原作者为

	lutaoquan2012 ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็有朋自远方而来，虽远必诛，杀无赦

搬运于2025-08-24 21:28:04，当前版本为作者最后更新于2024-01-16 14:46:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：

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

按照样例解释一下：

..........
..........
..........
..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;
}