AcWing 1470. 水桶传递队列
原题链接
简单
作者:
ComistryMo
,
2022-03-29 15:48:23
,
所有人可见
,
阅读 188
题目:
农场上起火了,奶牛们正在紧急赶去灭火!
农场可以用一个像这样的 10×10 的字符方阵来描述:
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
字符’B’表示正着火的牛棚,字符’L’表示一个湖,而字符’R’表示农场上的一块巨大岩石。
奶牛们想要沿着一条湖到牛棚之间的路径组成一条“水桶传递队列”,这样她们就可以沿着这条路径传递水桶来帮助灭火。
当两头奶牛在东南西北四个方向上相邻时水桶可以在她们之间传递。
湖边的奶牛也是如此——奶牛只能在紧挨着湖的时候才能用水桶从湖里取水。
类似地,奶牛只能在紧挨着牛棚的时候才能用水去灭牛棚的火。
请帮助求出奶牛们为了组成这样的“水桶传递队列”需要占据的’.’格子的最小数量。
奶牛不能站在岩石所在的方格之内,此外保证牛棚和湖不是相邻的。
输入格式
输入包含 10 行,每行 10 个字符,描述这个农场的布局。
输入保证图案中恰有一个字符’B’、一个字符’L’以及一个字符’R’。
输出格式
输出一个整数,为组成一条可行的水桶传递队列所需要的奶牛的最小数量。
输入样例:
..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........
输出样例:
7
样例解释
在这个例子中,以下是一个可行的方案,使用了最小数量的奶牛(7):
..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........
题解:
#include<bits/stdc++.h>
using namespace std;
const int N = 11;
typedef pair<int ,int>PII;
// g[N][N]用来储存地图,d[N]][N]用来储存距离
char g[N][N];
int d[N][N];
//队列
PII q[N * N];
int lx, ly;
void bfs(){
//实现队列
int hh = 0, tt = -1;
//加入队头元素
q[++ tt] = {lx, ly};
//初始化d数组,即所有点到起点距离都是-1,起点自身距离为0
memset(d, -1, sizeof d);
d[lx][ly] = 0;
//记录偏移量
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (hh <= tt){
auto t = q[hh ++];
//拓展队列
for (int i = 0; i < 4; i ++){
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < 10 && y >= 0 && y < 10 && g[x][y] != 'R' && d[x][y] == -1){
if (g[x][y] == 'B'){
cout << d[t.first][t.second];
return;
}
d[x][y] = d[t.first][t.second] + 1;
q[++ tt] = {x, y};
}
}
}
}
int main(){
for (int i = 0; i < 10; i ++)
for (int j = 0; j < 10; j ++){
cin >> g[i][j];
//记录下湖的位置,也即即将用到的队头
if (g[i][j] == 'L')
lx = i, ly = j;
}
bfs();
return 0;
}