HDU 2612 Find a way

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.

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2612

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 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

大意

Y和M两个人要在任意一个KFC见面，求两人路径和中最短的一个

思路

两次BFS求出两人到所有KFC的路径长，再找出和最短的那个

Code

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int inf = 0x3f3f3f3f;

///BFS需要以结构体形式将数据临时存起来以备后来去遍历
///DFS没有要存储的临时数据
///由于DFS要用到递归，我感觉比BFS思想更复杂些
int n, m, ydex, ydey, mdex, mdey;
string s[205];
bool vis[205][205];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct node
{
    int x, y, step;
};

int tot;///kfc的a[]辅助，计总个数
struct kfc
{
    int x, y, y_step, m_step, tot_step;
} a[40005];

void kfc_init()
{
    for(int i = 0; i < 205; ++i)
    {
        a[i].y_step = inf;
        a[i].m_step = inf;
    }
}

///BFS擅长于最小（短）值，DFS擅长于连接体（相连）问题
void bfs(int x, int y, bool flag)///写之前一定想好bfs还是dfs
{
    int cnt = 0;///若是DFS(有递归属性)，不要在函数里定义啥
    vis[x][y] = 1;
    queue<node> q;
    node now;
    now.x = x;
    now.y = y;
    now.step = 0;
    q.push(now);
    while(q.size())
    {
        now = q.front();
        q.pop();
        if(s[now.x][now.y] == '@')
        {
            cnt++;
            for(int i = 0; i < tot; ++i)
            {
                if(a[i].x == now.x && a[i].y == now.y)
                {
                    if(flag == 0)
                        a[i].y_step = now.step;
                    else
                        a[i].m_step = now.step;
                    break;
                }
            }
            if(cnt == tot)
                return ;
        }

        for(int i = 0; i < 4; ++i)
        {
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
            if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && s[xx][yy] != '#')
            {
                vis[xx][yy] = 1;
                node nxt;
                nxt.x = xx;
                nxt.y = yy;
                nxt.step = now.step + 1;
                q.push(nxt);
            }
        }
    }
}

int main()
{
//    freopen("00in.txt", "r", stdin);
    while(~scanf("%d%d", &n, &m))
    {
        kfc_init();
        tot = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; ++i)
            cin >> s[i];

        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(s[i][j] == 'Y')
                {
                    ydex = i;
                    ydey = j;
                }
                if(s[i][j] == 'M')
                {
                    mdex = i;
                    mdey = j;
                }
                if(s[i][j] == '@')
                {
                    a[tot].x = i;
                    a[tot].y = j;
                    tot++;
                }
            }

        bfs(ydex, ydey, 0);
        memset(vis, 0, sizeof(vis));
        bfs(mdex, mdey, 1);

        int ans = inf;
        for(int i = 0; i < tot; ++i)
        {
            a[i].tot_step = a[i].y_step + a[i].m_step;
            if(ans > a[i].tot_step)
                ans = a[i].tot_step;
        }
        cout << ans * 11 << '\n';
    }
    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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

突然发现DFS比BFS更难以梳理清楚、难实现，因为涉及递归……

相较于DFS，BFS就显得友好多了……