【題目描述】

CCY所在的城市可以用一個N*M(N,M <= 50)的地圖表示，地圖上有五種符號：“. * X D S”。其中，“X”表示石頭，水和人都不能從上面經(jīng)過，“.”表示平原，CCY和洪水都可以經(jīng)過，“*”表示洪水開始的地方（可能有多個地方同時開始發(fā)生洪水），“D”表示CCY的別墅，“S”表示CCY現(xiàn)在的位置。

CCY每分鐘可以向相鄰位置移動，而洪水將會在CCY移動之后把相鄰的沒有洪水的土地淹沒（從已淹沒的土地）。

先詢問CCY回到別墅的最少時間。

【輸入描述】

第一行輸入兩個整數(shù)N和M(N，M <= 50)；

接下來輸入一個N*M的字符矩陣，表示CCY所在城市的地圖。

【輸出描述】

輸出一個整數(shù)，表示CCY回到別墅需要的最少時間，如果無解，輸出-1。

【輸入樣例】

3 3

D.*

...

.S.

【輸出樣例】

3

【數(shù)據(jù)范圍及提示】

先BFS出每個點被水淹沒的時間，然后再次BFS。

源代碼：#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
queue <int> Q;
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
int m,n,End1,End2,Start1,Start2,i[51][51];
int main() //細(xì)節(jié)巨多的BFS題，做搜索還得三思而后行。
{memset(i,0x3f,sizeof(i));scanf("%d%d\n",&n,&m);for (int a=1;a<=n;a++){char S[51];scanf("%s",S+1); //看來NOIP字符串輸入就靠它了。for (int b=1;b<=m;b++){if (S[b]=='D'){End1=a;End2=b;i[a][b]=0; //洪水無法到達(dá)的標(biāo)記。
            }if (S[b]=='S'){Start1=a;Start2=b;}if (S[b]=='X')i[a][b]=0;if (S[b]=='*'){i[a][b]=0;Q.push(a);Q.push(b);}}}while (!Q.empty()){int X=Q.front(); //新奇的隊列用法，值得學(xué)習(xí)。
        Q.pop();int Y=Q.front();Q.pop();for (int a=0;a<4;a++){int t1=X+x[a];int t2=Y+y[a];if (!t1||!t2||t1>n||t2>m||i[t1][t2]!=i[0][0]) //不能走的。continue;i[t1][t2]=i[X][Y]+1;Q.push(t1);Q.push(t2);}}Q.push(0);Q.push(Start1);Q.push(Start2);while (!Q.empty()){int t=Q.front();Q.pop();int X=Q.front();Q.pop();int Y=Q.front();Q.pop();for (int a=0;a<4;a++){int t1=X+x[a];int t2=Y+y[a];if (t1==End1&&t2==End2){printf("%d",t+1);return 0;}if (!t1||!t2||t1>n||t2>m||i[t1][t2]<=t+1) //走過了或者洪水早已沒過。continue;i[t1][t2]=0; //先到就是最優(yōu)，直接標(biāo)記不能返回。Q.push(t+1);Q.push(t1);Q.push(t2);}}printf("ORZ hzwer!!!");return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/Ackermann/p/5448275.html

總結(jié)

以上是生活随笔為你收集整理的洪水的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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