Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description - 题目描述
经过一年在杭州的学习，yifenfei终于回到了家乡宁波。离开宁波一年，yifenfei有许多人需要拜访。特别是好基友Merceki。
Yifenfei家住郊区，然而Merceki则住在市中心。因此yifenfei打算约Merceki在KFC面基，不过他们要选一家到达所花费的时间和最短的店。
现在给你一张宁波地图，yifenfei和Merceki可以花费11分钟分别进行上下左右移动。
输入有多组测试用例。 每组用例开头为两个整数n，m。（2<=n,m<=200） 随后n行，每行有m个字符。 ‘Y’表示yifenfei 的初始位置。 ‘M’表示Merceki 的初始位置。 ‘#’障碍物 ‘.’道路 ‘@’ KCF
Output - 输出
对于每个测试用例，输出yifenfei 与Merceki 到达某个KFC最少的二者时间和。至少存在一个KFC让他们相遇。
Sample Input - 输入样例
4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...#
Sample Output - 输出样例
66 88 66
题解
BFS套路，扫两遍出结果。
需要注意无法达到的KFC，可以通过处理最大值来规避。
代码 C++
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define INF 0x01010101 6 struct Point{ 7 int y, x; 8 }st1, st2, kfc[405], now, nxt; 9 std::queue<Point> q; 10 int data[205][205], iK, len[405], fx[8] = { 1, 0, -1, 0, 0, 1, 0, -1 }; 11 char map[205][205]; 12 void BFS(char c, char b){ 13 int i, tmp; 14 while (!q.empty()){ 15 now = q.front(); q.pop(); tmp = data[now.y][now.x] + 1; 16 for (i = 0; i < 8; i += 2){ 17 nxt.y = now.y + fx[i]; nxt.x = now.x + fx[i + 1]; 18 if (map[nxt.y][nxt.x] == c){ 19 data[nxt.y][nxt.x] = tmp; map[nxt.y][nxt.x] = b; 20 q.push(nxt); 21 } 22 } 23 } 24 for (i = 0; i < iK; ++i) len[i] += data[kfc[i].y][kfc[i].x]; 25 } 26 int main(){ 27 int n, m, i, j, opt; 28 while (~scanf("%d%d ", &n, &m)){ 29 memset(map, ‘#‘, sizeof map); memset(len, 0, sizeof len); 30 iK = 0; opt = INF; 31 for (i = 1; i <= n; ++i) gets(&map[i][1]); 32 for (i = 1; i <= n; ++i) for (j = 1; j <= m; ++j){ 33 switch (map[i][j]){ 34 case ‘Y‘: st1 = { i, j }; map[i][j] = ‘.‘; break; 35 case ‘M‘: st2 = { i, j }; map[i][j] = ‘.‘; break; 36 case ‘@‘: kfc[iK++] = { i, j }; map[i][j] = ‘.‘; 37 } 38 } 39 40 memset(data, INF, sizeof data); 41 q.push(st1); data[st1.y][st1.x] = 0; map[st1.y][st1.x] = ‘*‘; 42 BFS(‘.‘, ‘*‘); 43 44 memset(data, INF, sizeof data); 45 q.push(st2); data[st2.y][st2.x] = 0; map[st2.y][st2.x] = ‘X‘; 46 BFS(‘*‘, ‘X‘); 47 48 for (i = 0; i < iK; ++i) opt = std::min(opt, len[i]); 49 printf("%d\n", opt * 11); 50 } 51 return 0; 52 }
原文：http://www.cnblogs.com/Simon-X/p/6399193.html