1. 题目

传送门= ̄ω ̄=

2. 题解

首先要想到一个XZY发现不了的性质:

这题可以枚举起点和终点而不会超时。

然后还要发现一个XZY发现不了的性质:

可以用01BFS/迪杰斯特拉快速算出联通两点需要多少次移除障碍的机(ji)会(fei)。

我们只需要枚举起点,然后从这个点出发跑一遍01BFS计算出这个点到其他的点联通需要多少次移除障碍的机(ji)会(fei)就行了。

然后枚举起点终点,看联通它们需要的机(ji)会(fei)是否小于等于$T$

复杂度$O(n ^ 4)$,不虚

代码:

#include <bits/stdc++.h>

#define NS (35)

using namespace std;

const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, t, dis[NS * NS][NS * NS], ans;

bool vis[NS * NS];

char str[NS][NS];

inline int H(int a, int b) {return (a - 1) * m + b;}

list<int> que;

void Bfs(int a, int b)
{
    int X = H(a, b);
    memset(dis[X], 127, sizeof(dis[X])), memset(vis, 0, sizeof(vis));
    dis[X][X] = str[a][b] - '0', que.push_back(H(a, b));
    while (!que.empty())
    {
        int F = *que.begin(); que.pop_front();
        if (vis[F]) continue;
        vis[F] = 1, a = (F - 1) / m + 1, b = (F - 1) % m + 1;
        for (int i = 0, na, nb, nx; i < 4; i += 1)
        {
            na = a + dx[i], nb = b + dy[i], nx = H(na, nb);
            if (na < 1 || nb < 1 || na > n || nb > m) continue;
            if (str[na][nb] - '0')
            {
                if (dis[X][nx] > dis[X][F] + 1)
                    dis[X][nx] = dis[X][F] + 1, que.push_back(nx);
            }
            else if (dis[X][nx] > dis[X][F])
                dis[X][nx] = dis[X][F], que.push_front(nx);
        }
    }
}

inline int cal(int a, int b, int c, int d)
{
    return (a - c) * (a - c) + (b - d) * (b - d);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(t);
    for (int i = 1; i <= n; i += 1) scanf("%s", str[i] + 1);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= m; j += 1)
            Bfs(i, j);
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= m; j += 1)
            for (int x = 1; x <= n; x += 1)
                for (int y = 1; y <= m; y += 1)
                    if (dis[H(i, j)][H(x, y)] <= t)
                        ans = max(ans, cal(i, j, x, y));
    printf("%.6f\n", sqrt(ans));
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *