【HDU - 2612】Find a way（bfs）

-->Find a way

直接上Chinese

?Descriptions:

hsj和lsh最近迷上了pokemon go的游戲。在雙十一大物期中考試來臨之前，他們想抓一只稀有土撥鼠來攢攢人品（因為土撥鼠的刷新地點最近來到了哈工程）
但是由于土撥鼠過于強大，他的雷霆半月斬以及驚天浪濤沙都可以輕松的將他們兩擊敗，但是他們兩的合擊必殺技流影電光閃以及天羽屠鼠舞可以將土撥鼠打至昏迷狀態，并可將其捕獲。
但是因為這是款按時間付費的游戲，他們需要盡快捕捉到土撥鼠（即他們兩到土撥鼠的時間之和需要最少），因此他們找到了你來幫他們解決這個問題。 規定每走一步需要花費11分鐘。

Input

輸入存在多組（需使用！=EOF）
每組的第一行有兩個整數n,m（2<=n,m<=200）
接下來n行，每行包括m個字符
‘Y’表示hsj所在的位置
‘M’表示lsh所在的位置
‘.’表示可以通過的地方
‘#’表示教學樓即不能走的地方
‘@’表示稀有土撥鼠刷新的地方（地圖中存在多只稀有土撥鼠）
Output

對于每組樣例輸出他們到達土撥鼠刷新點的最小時間總和。
保證每組樣例都存在一個土撥鼠刷新點，他們兩都能到達?
Sample Input

4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#

Sample Output

66
88
66

題目鏈接：

https://vjudge.net/problem/HDU-2612

這可以說是一題兩個bfs

分別求出Y、M在這張地圖所有地方的所用時間，再求出在"@"地方的時間的最小值即可

具體操作看代碼

AC代碼

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int T,n,m;
char mp[1005][1005];//原始地圖
int vis[1005][1005];//記錄人是否走過
int ytime[1005][1005];//Y 經過這個地方的時間
int mtime[1005][1005];//M 經過這個地方的時間
int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1}};//四個方向
struct node
{int x,y;//坐標
};
node now,net;
node Y,M;
void bfs(int f)//人
{queue<node>q;MEM(vis,0);//都要初始化，都沒走過，設為0if(f==0)// Y的情況
    {MEM(ytime,INF);q.push(Y);vis[Y.x][Y.y]=1;ytime[Y.x][Y.y]=0;}if(f==1)// M的情況
    {MEM(mtime,INF);q.push(M);vis[M.x][M.y]=1;mtime[M.x][M.y]=0;}while(!q.empty())// bfs 一樣的套路
    {now=q.front();q.pop();for(int i=0; i<4; i++)//四個方向
        {net.x=now.x+dt[i][0];net.y=now.y+dt[i][1];if(net.x>=0&&net.x<n&&net.y>=0&&net.y<m&&!vis[net.x][net.y]&&mp[net.x][net.y]!='#')//滿足條件
            {q.push(net);//入隊vis[net.x][net.y]=1;//走過了if(f==0)//Y 的路線時間ytime[net.x][net.y]=ytime[now.x][now.y]+1;if(f==1)//M 的路線時間mtime[net.x][net.y]=mtime[now.x][now.y]+1;}}}
}
int main()
{while(cin>>n>>m){for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>mp[i][j];if(mp[i][j]=='Y'){Y.x=i;Y.y=j;}if(mp[i][j]=='M'){M.x=i;M.y=j;}}}bfs(0); //Y的路線bfs(1); //M的路線int ans=INF; //最小步數for(int i=0; i <n; i++)//搜一遍地圖，看一下"@"所在地方的時間之和，取最小值for(int j=0; j<m; j++)if(mp[i][j]=='@')ans=min(ans,ytime[i][j]+mtime[i][j]);cout<<11*ans<<endl;}return 0;
}

?