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

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

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

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