HDU - 2612 Find a way 【BFS】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2612

题意

有两个人要去一个城市中的KFC 一个城市中有多个KFC 求两个人到哪一个KFC的总时间最少求出这个最少的总时间

思路

用BFS打一遍表求出两个人每人到每个 KFC 的时间然后遍历一下更新答案

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1);

const double E = exp(1);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 5e4 + 5;

const int MOD = 1e9 + 7;

int Move[][2]

{

    -1, 0, // up

     1, 0, // down

     0,-1, // left

     0, 1, // right

};

struct Node

{

    int x, y, step;

}tmp;

string G[205];

int v[205][205];

int dis[205][205][2];

int n, m;

int sx[2], sy[2];

queue <Node> q;

bool ok(int x, int y)

{

    if (x < 0 || x >= n || y < 0 || y >= m || G[x][y] == '#' || v[x][y] == 1)

        return false;

    return true;

}

void bfs(int vis)

{

    while (!q.empty())

    {

        int x = q.front().x;

        int y = q.front().y;

        int step = q.front().step;

        q.pop();

        if (G[x][y] == '@')

            dis[x][y][vis] = min(dis[x][y][vis], step);

        for (int i = 0; i < 4; i++)

        {

            tmp.x = x + Move[i][0];

            tmp.y = y + Move[i][1];

            tmp.step = step + 1;

            if (ok(tmp.x, tmp.y))

            {

                q.push(tmp);

                v[tmp.x][tmp.y] = 1;

            }

        }

    }

}

int main()

{

    while (~scanf("%d%d", &n, &m))

    {

        for (int i = 0; i < n; i++)

        {

            cin >> G[i];

            for (int j = 0; j < m; j++)

            {

                if (G[i][j] == 'Y')

                {

                    sx[0] = i;

                    sy[0] = j;

                }

                else if (G[i][j] == 'M')

                {

                    sx[1] = i;

                    sy[1] = j;

                }

            }

        }

        memset(dis, 0x3f, sizeof(dis));

        for (int i = 0; i < 2; i++)

        {

            CLR(v);

            tmp.x = sx[i];

            tmp.y = sy[i];

            v[tmp.x][tmp.y] = 1;

            tmp.step = 0;

            while (!q.empty())

                q.pop();

            q.push(tmp);

            bfs(i);

        }

        int ans = INF;

        for (int i = 0; i < n; i++)

        {

            for (int j = 0; j < m; j++)

            {

                if (G[i][j] == '@')

                    ans = min(ans, dis[i][j][0] + dis[i][j][1]);

            }

        }

        cout << ans * 11 << endl;

    }

}

巴特西

HDU - 2612 Find a way 【BFS】

最新文章

热门文章