?

?沼躍魚早已看穿了一切

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?593??Solved:?229
[Submit][Status][Web Board]

Description

?沼躍魚打開密碼門后發現門后是一個像迷宮一樣的房間，墻上的指示牌寫著：房間內某處有一寶箱，但是寶箱被上鎖了，鑰匙在這個房間的某個角落。沼澤魚對寶箱里有什么很感興趣，但它必須先去拿到鑰匙才可以打開寶箱。然而沼躍魚早已看穿了一切，它看清了這個房間的布局，現在給出房間的布局圖，問沼躍魚拿到鑰匙并打開寶箱最少需要走多少步。沼躍魚每次只能向上、下、左、右中其中一個方向走一步，但若那個位置是墻時則不能往那個位置走（顯然，沼躍魚不能穿墻）。

Input

輸入的第一行是一個整數T(0<T<20),代表接下來有T組數據。

?每組數據的第一行有兩個整數n,m(0<n,m≤10)，n代表房間的寬度，m代表房間的長度。

接下來n行，每行有m個字符，‘S’表示開始時沼躍魚所處的位置，‘#’代表墻，‘*’代表空地，‘K’代表鑰匙，‘B’表示寶箱。鑰匙只有一把。

詳情參看樣例輸入。

Output

?對于每組數據，輸出一行包含一個整數x，x代表沼躍魚拿到鑰匙并打開寶箱所需的最少步數。若沼躍魚不能夠拿到鑰匙并打開寶箱（即到達不了鑰匙或寶箱所在處）則輸出-1。

Sample Input

1 5 6 ***#B# S**#*# ##***# K#*#*# ***#*#

Sample Output

17

HINT

?

對于樣例數據，房間寬5個單位，長6個單位。

從S出發到K需要的最少步數為8，而從K出發到B所需的最少步數為9.

所以答案為8 + 9 = 17.

請使用scanf("%s", s);或cin>> s;來讀取字符串以避免出現漏讀多讀的情況。

?

BFS 廣度優先搜索

CODE :

#include<iostream> #include<cstring> #include<cstdio> using namespace std; int b[15][15]; void bfs(int n,int m,int num) {for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(b[i][j]==num){if(b[i][j+1]==0){b[i][j+1]=num+1;}if(b[i][j-1]==0){b[i][j-1]=num+1;}if(b[i-1][j]==0){b[i-1][j]=num+1;}if(b[i+1][j]==0){b[i+1][j]=num+1;}}}} } int main() {int N;cin>>N;while(N--){char a[15][15];int n,m;cin>>n>>m;memset(b,-1,sizeof(b));int x0,y0,x1,y1;for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]!='#'){b[i][j]=0;}if(a[i][j]=='S'){b[i][j]=1;}if(a[i][j]=='K'){x0=i;y0=j;}}}int num=1;while(b[x0][y0]==0&&num<75){bfs(n,m,num);num++;/*for(int i=1;i<=n;i++){ for (int j=1;j<=m;j++){cout<<b[i][j]<<'\t';}cout<<endl;}cout<<endl;*/}if(num>74){cout<<"-1"<<endl;continue;}for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){if(a[i][j]!='#'){b[i][j]=0;}if(a[i][j]=='K'){b[i][j]=1;}if(a[i][j]=='B'){x0=i;y0=j;}}}/* for(int i=1;i<=n;i++){ for (int j=1;j<=m;j++){cout<<b[i][j]<<'\t';}cout<<endl;}*/int num0=1;while(b[x0][y0]==0&&num0<75){bfs(n,m,num0);num0++;///*for(int i=1;i<=n;i++) //{ // for (int j=1;j<=m;j++)// {// cout<<b[i][j]<<'\t';// }// cout<<endl;//}*///cout<<endl; }if(num0>74){cout<<"-1"<<endl;continue;}cout<<num+num0-2<<endl;} }

?

轉載于:https://www.cnblogs.com/guofeng1022/p/4220565.html

總結

以上是生活随笔為你收集整理的沼跃鱼早已看穿了一切 C/C++的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。