2020.2.22GDUT寒假训练排位赛2-G
G — Bucket Brigade
题目大意： 农场失火了，牛都跑去把火扑灭!农场是由一个10×10的网格来描述的，就像这样:
文章图片
字母“B”代表刚刚着火的谷仓。“L”代表一个湖，“R”代表一块大石头的位置。奶牛们想要组成一个“水桶旅”，把自己安置在湖和谷仓之间的一条小路上，这样它们就可以沿着小路传递一桶桶的水来帮助灭火。如果牛在北、南、东、西四个方向相邻，那么桶可以在它们之间移动。奶牛只有在紧挨着湖的地方才能从湖里汲取一桶水。同样的，奶牛只有在靠近谷仓的地方才能把一桶水泼到谷仓上。请帮忙确定’的最小数量“广场应该被奶牛占领，形成一个成功的旅。奶牛不能在有大石头的广场上，而且谷仓和湖泊也不能紧挨着。
输入
包含10行，每行10个字符，描述了农场的布局。
输出
输出一个整数，给出组成一个可行的斗旅所需的最小奶牛数。
文章图片
题目分析： 【2020.2.22GDUT寒假训练排位赛2-G】最短路径，经典的广搜题
代码实现：
#include
#include
#include
#include
using namespace std;
int li,lj,bi,bj;
char farm[15][15];
int farm1[15][15] = {0};
//farm[i][j] i和j的距离
int ffxx[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
//四个方向
queueqx,qy;
void init()
{
for(int i=1;
i<=10;
i++){
for(int j=1;
j<=10;
j++){
farm1[i][j] = 99999999;
}
}
}
int bfs()
{
farm1[li][lj] = 0;
while(!qx.empty())
{
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
if(farm[x][y]=='B') break;
for(int i=0;
i<4;
i++){
int x1 = x+ffxx[i][0];
int y1 = y+ffxx[i][1];
if(1<=x1 && x1<=10 && 1<=y1 && y1<=10 && farm[x1][y1]!='R' && farm1[x1][y1]==99999999){
qx.push(x1);
qy.push(y1);
farm1[x1][y1] = farm1[x][y]+1;
}
}
}
return farm1[bi][bj];
}int main()
{
init();
//初始化
for(int i=1;
i<=10;
i++){
for(int j=1;
j<=10;
j++){
scanf("%c",&farm[i][j]);
if(farm[i][j]=='L'){
li = i;
lj = j;
}
if(farm[i][j]=='B'){
bi = i;
bj = j;
}
}
getchar();
}
qx.push(li);
qy.push(lj);
printf("%d\n",bfs()-1);
//广搜return 0;
} 推荐阅读
- 绘本讲师训练营【24期】14/21阅读原创《小黑鱼》
- 绘本讲师训练营【18期】14/21《我的情绪小怪兽》故事会新体验
- 合理情绪疗法之试用｜李克富思维训练营56/90
- 绘本讲师训练营7期9/21阅读原创《蜗牛屋|绘本讲师训练营7期9/21阅读原创《蜗牛屋 》
- 拆书方法训练营
- 阿菘的ScalersTalk第五轮新概念朗读持续力训练Day15|阿菘的ScalersTalk第五轮新概念朗读持续力训练Day15 20191025
- 特种兵训练第四天
- 2018-09-03(李克富视角点评训练营81/90)|2018-09-03(李克富视角点评训练营81/90) 那只蛙从“井”爬出来又进入了“隧道”
- 学员+3组杨子涓+202002RIA训练营W3D2+苏格拉底提问法
- 绘本讲师训练营【28期】15/21阅读原创《活了100万次的猫》