水桶傳遞隊(duì)列

突然想到小學(xué)時(shí)候玩的推箱子游戲（還拿了科技節(jié)全市第一hhh）

推箱子比賽的評(píng)判規(guī)則就是同一道題誰(shuí)用的步數(shù)少，在步數(shù)相同的情況下，用時(shí)短的同學(xué)獲勝嘿嘿

當(dāng)時(shí)準(zhǔn)備比賽的時(shí)候，把推箱子所有的關(guān)數(shù)都破解了！

原來(lái)我和計(jì)算機(jī)的緣分這么早就結(jié)下了呀~

題目

農(nóng)場(chǎng)上起火了，奶牛們正在緊急趕去滅火！

農(nóng)場(chǎng)可以用一個(gè)像這樣的 10×10 的字符方陣來(lái)描述：

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

字符’B’表示正著火的牛棚，字符’L’表示一個(gè)湖，而字符’R’表示農(nóng)場(chǎng)上的一塊巨大巖石。

奶牛們想要沿著一條湖到牛棚之間的路徑組成一條“水桶傳遞隊(duì)列”，這樣她們就可以沿著這條路徑傳遞水桶來(lái)幫助滅火。

當(dāng)兩頭奶牛在東南西北四個(gè)方向上相鄰時(shí)水桶可以在她們之間傳遞。

湖邊的奶牛也是如此——奶牛只能在緊挨著湖的時(shí)候才能用水桶從湖里取水。

類(lèi)似地，奶牛只能在緊挨著牛棚的時(shí)候才能用水去滅牛棚的火。

請(qǐng)幫助求出奶牛們?yōu)榱私M成這樣的“水桶傳遞隊(duì)列”需要占據(jù)的’.’格子的最小數(shù)量。

奶牛不能站在巖石所在的方格之內(nèi)，此外保證牛棚和湖不是相鄰的。

輸入格式

輸入包含 10 行，每行 10 個(gè)字符，描述這個(gè)農(nóng)場(chǎng)的布局。

輸入保證圖案中恰有一個(gè)字符’B’、一個(gè)字符’L’以及一個(gè)字符’R’。

輸出格式

輸出一個(gè)整數(shù)，為組成一條可行的水桶傳遞隊(duì)列所需要的奶牛的最小數(shù)量。

輸入樣例：

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

輸出樣例：

7

樣例解釋

在這個(gè)例子中，以下是一個(gè)可行的方案，使用了最小數(shù)量的奶牛（7）：

.......... .......... .......... ..B....... ..C....... ..CC.R.... ...CCC.... .....C.... .....L.... ..........

思路

Flood Fill (DFS、BFS)

如果起點(diǎn)和終點(diǎn)不在同一行也不在同一列的話，不管障礙物在什么地方，都一定可以找到一條最短路徑，最短路徑的長(zhǎng)度就是L和B之間的曼哈頓距離

如果L和B在同一行或同一列，障礙物X不在L和B之間的話，也可以取到理論最小值（曼哈頓距離長(zhǎng)度）

如果L和B在同一行或同一列，障礙物X在L和B之間，最短距離為曼哈頓距離+2

注：最后求得的格子數(shù)=最短路徑的距離-1

AC代碼

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm>using namespace std;int main() {int x1,y1,x2,y2,x3,y3;//x1,y1表示起點(diǎn);x2,y2表示障礙物;x3,y3表示終點(diǎn)char s[11];//為"\0"留出空間for(int i=0;i<10;i++){cin>>s;for(int j=0;j<10;j++){char c=s[j];if(c=='L'){x1=i,y1=j;}else if(c=='R'){x2=i,y2=j;}else if(c=='B'){x3=i,y3=j;}}} int res=abs(x1-x3)+abs(y1-y3);if(x1==x2&&x2==x3&&(y2-y1)*(y2-y3)<0|| y1==y2&&y2==y3&&(x2-x1)*(x2-x3)<0)//在同一列并且y2在y1與y3之間（相當(dāng)于 y2-y1 與 y2-y3 符號(hào)相反，則(y2-y1)*(y1-y3)<0） {res+=2;} cout<<res-1<<endl;//求的不是最短距離而是起點(diǎn)和終點(diǎn)之間差了多少個(gè)格子 //格子數(shù)=最短路徑的距離-1 return 0; }

總結(jié)

以上是生活随笔為你收集整理的水桶传递队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。