HDU 2612 - Find a way（两遍广搜）

---

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.
‘@’ KFC

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 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Sample Output

66
88
66
1
2
3

---

题目大意
地图上有很多家KFC店，Y同学和M同学约定到同一家KFC店就餐，他们只能上下左右地移动，每移动一格需要11分钟，#表示不能走的路，.表示可以走的路，@表示KFC点的坐标，并且给定了这两名同学的坐标，现在题目要求是，找到一个最近的KFC店走法，使得他们分别到那家店的时间之和最小。

很显然，就是对Y同学和M同学各进行一遍bfs，然后将他们到各个kfc门店的最短距离给记录下来

int Y_to_kfc[N][N], M_to_kfc[N][N]; //分别映射Y、M走到各个kfc点的距离

然后对于每组Y_to_kfc[x][y] + M_to_kfc[x][y]$(x,y)\in kfc$取一个min就可以了。

注*：这里有个坑点，并不是每个kfc门店都是Y、M可以到达的，所以要对Y(M)_to_kfc初始化为无穷大0x3f3f3f3f，因为如果每次找到的$(x,y)\in kfc$是0，说明并不可达，取min会对结果造成影响。

C++代码

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef struct node{
    int x, y, dist;
}Node;

const int N = 210;

char g[N][N];
bool st[N][N];
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int Y_to_kfc[N][N], M_to_kfc[N][N];        //分别映射Y、M走到各个kfc点的距离
int n, m;
queue<Node> q;

bool check(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] != '#' && !st[x][y];
}

void bfs(int startX, int startY, int dis[][N]){     //除了'@'那里，其他基本是模板
    Node start;     //起点
    start.x = startX, start.y = startY, start.dist = 0;
    q.push(start);
    st[startX][startY] = true;

    while(!q.empty()){
        Node t = q.front();
        q.pop();

        if(g[t.x][t.y] == '@')         //记录一个到kfc的距离
            dis[t.x][t.y] = t.dist;

        for(int i = 0;i < 4;i ++){
            int nex = t.x + dx[i], ney = t.y + dy[i];
            if(check(nex, ney)){
                st[nex][ney] = true;
                Node nextp;
                nextp.x = nex, nextp.y = ney, nextp.dist = t.dist + 1;
                q.push(nextp);
            }
        }
    }
}

int main(){
    ios :: sync_with_stdio(false);

    while(cin >> n >> m){
        //坑点：一定要memset，因为有些kfc点不一定是可以到达的，因为这个WA了不下五发
        memset(Y_to_kfc, 0x3f3f3f3f, sizeof Y_to_kfc);
        memset(M_to_kfc, 0x3f3f3f3f, sizeof M_to_kfc);

        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                cin >> g[i][j];
            
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++){
                if(g[i][j] == 'M'){
                    memset(st, false, sizeof st);
                    bfs(i, j, M_to_kfc);
                }
                else if(g[i][j] == 'Y'){
                    memset(st, false, sizeof st);
                    bfs(i, j, Y_to_kfc);
                }
            }

        int ans = 0x3f3f3f3f;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                if(g[i][j] == '@')          //这里'@'不一定是Y或M都可达的，0x3f3f3f3f可以排掉干扰
                    ans = min(ans, Y_to_kfc[i][j] + M_to_kfc[i][j]);

        cout << ans * 11 << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86