點擊打開鏈接

Find a way

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 21857????Accepted Submission(s): 7120


Problem Description Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.

Input The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ ?? express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF

Output For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.
Sample Input 4 4Y.#@.....#..@..M4 4Y.#@.....#..@#.M5 5Y..@..#....#...@..M.#...# Sample Output 668866 Author yifenfei
Source 奮斗的年代
Recommend yifenfei???|???We have carefully selected several similar problems for you:??2717?1254?1728?2102?1072

題意：

給一張地圖，Y代表第一個人所在的位置，M代表第二個人所在的位置，.代表路，#代表墻，@代表KFC， 兩個人想在同一個kfc見面，問他們見面花費最小的時間；

分析：

遍歷地圖，對于每一KFC，分別求出Y到這個KFC的距離dy，M到這個KFC的距離dm， 如果距離為dy=-1或者dm=-1，則說明無法到達； 否則，跟新最短距離：ans=min(ans,dy+dm);

這個思路比較簡單，但是當KFC的數量非常多的時候，就會超時

根據上面的思路，我們可以優化一下，減少重復計算，設置一個距離數組dis[N][N][2];初始化為INF

dis[i][j][0]代表Y到坐標為（i，j）的KFC的距離，dis[i][j][1]代表M到坐標為（i，j）的KFC的距離

然后，BFS求出Y到地圖上所有點的最短距離，若這個點是KFC，則更新dis[i][j][0],

同理，BFS求出M到地圖上所有點的最短距離，若這個點是KFC，則更新dis[i][j][1],

最后遍歷地圖，如果這個點是KFC，且當前最短距離 > Y到這個KFC的距離+M到這個KFC的距離，

則更新最短距離，最后不要忘記*11哦

超時代碼

#include<iostream> #include<cstring> #include<queue> #include<cmath> #include<cstdio> using namespace std; #define MAXV 209 char mp[MAXV][MAXV];//地圖 bool vis[MAXV][MAXV];//判斷點是否在隊列 int n,m; struct point {int x,y,step; }; point Y,M;//兩人的位置 vector<point> KFC;//儲存KFC的位置 int dic[4][2]={0,1,0,-1,1,0,-1,0}; bool check(int x,int y)//若這一點可以走，返回0 {if(x<0||x>=n||y<0||y>=m||vis[x][y]||mp[x][y]=='#')return 1;return 0; } int bfs(point s,point e)//求s點到e點的最短距離，無法到達距離為-1 {memset(vis,0,sizeof(vis));queue<point>q;q.push(s);//起點入隊vis[s.x][s.y]=1;while(!q.empty()){point now=q.front();q.pop();if(now.x==e.x&&now.y==e.y)//已經到達終點return now.step;for(int i=0;i<4;i++)//上下左右，四個方向搜索{int x=now.x+dic[i][0];int y=now.y+dic[i][1];if(check(x,y))//不合法continue;point next;next.x=x;next.y=y;next.step=now.step+1;vis[x][y]=1;q.push(next);}}return -1;//無法到達 } int main() {while(scanf("%d%d",&n,&m)!=EOF){KFC.clear();for(int i=0;i<n;i++){scanf("%s",mp[i]);for(int j=0;j<m;j++){if(mp[i][j]=='Y'){Y.x=i;Y.y=j;Y.step=0;}if(mp[i][j]=='M'){M.x=i;M.y=j;M.step=0;}if(mp[i][j]=='@'){point temp;temp.x=i;temp.y=j;temp.step=0;KFC.push_back(temp);}}}int ans=1<<20;for(int i=0;i<KFC.size();i++)//遍歷所有KFC{int dy=bfs(Y,KFC[i]),dm=bfs(M,KFC[i]);if(dy==-1||dm==-1)continue;ans=min(ans,dy+dm);}cout<<ans*11<<endl;}return 0; }
AC代碼
#include<iostream> #include<queue> #include<cstdio> #include<cstring> using namespace std; const int N = 210; const int inf = 100000000; int n, m, flag;//flag=0代表Y，flag=1代表M int dis[N][N][2]; //dis[i][j][0]代表Y到坐標為（i，j）的KFC的距離 //dis[i][j][1]代表M到坐標為（i，j）的KFC的距離 int mark[N][N];//標記點是否在隊列中 int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};//搜索方向 char s[N][N];//地圖 struct node {int x, y, step; }; void bfs(int x, int y) {queue<node>q;node temp, type;temp.x = x;temp.y = y;temp.step = 0;q.push(temp);//起點入隊mark[x][y] = 1;//標記while(!q.empty()){temp = q.front();q.pop();//出隊type.step = temp.step + 1;//步數加一for(int i = 0; i < 4; i++){type.x = x = temp.x + dir[i][0];type.y = y = temp.y + dir[i][1];if(x >= 0 && x < n && y >= 0 && y < m && mark[x][y] == 0 && s[x][y]!='#')//可以走{mark[x][y] = 1;if(s[x][y] == '@')dis[x][y][flag] = type.step;//距離q.push(type);}}} } int main() {while(scanf("%d%d", &n, &m)!=EOF){int min = inf;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)dis[i][j][0] = dis[i][j][1] = inf;//初始化距離為INFfor(int i = 0; i < n; i++)scanf("%s", s[i]);for(int i = 0; i < n; i++)for(int j = 0; j < m; j++){if(s[i][j] == 'Y'){flag = 0;memset(mark, 0, sizeof(mark));bfs(i, j);}if(s[i][j] == 'M'){flag = 1;memset(mark, 0, sizeof(mark));bfs(i, j);}}for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(s[i][j] == '@' && min > dis[i][j][0] + dis[i][j][1])//松馳操作{min = dis[i][j][0] + dis[i][j][1];//更新最短距離}printf("%d\n", min*11);} }

總結

以上是生活随笔為你收集整理的HDU 2612 Find a way bfs的全部內容，希望文章能夠幫你解決所遇到的問題。

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