专栏首页用户6093955的专栏Artwork (Gym - 102346A)【DFS、连通块】

Artwork (Gym - 102346A)【DFS、连通块】

Artwork (Gym - 102346A)

题目链接

算法

DFS,连通块

时间复杂度:O(k*n + k * k)

1.这道题就是让你判断从(0,0)到(m,n),避开中途所有的传感器(传感器的检测范围为半径为s的圆)的检测区域,最终能否到达(m,n)。

2.这道题很容易想到圆与圆相切或相交最后把能出去的路全堵上了,具体是把上下、左右、左下、右上这四个边界给堵掉一部分(只要满足前面四种情况的其中一个,就过不去)。见下图。

很明显,这样堵绝对出不去。然而方法是有,但怎么实现它呢?由于当时以为这是个复杂的计算几何的题,结果看了半天计算几何模板却无从下手(其实只涉及了一点计算几何的知识,就是判断两个圆是否相交或相切),最终未果。查阅了一些解题博客后了解到该题可以用DFS,连通块的思想来实现,当然还有是用并查集实现,不过并没有看并查集是怎么实现它的,这里先只介绍如何用DFS来实现它。

3.首先应明确一点,就是如何判断两圆是否相交或相切,即圆心之间的距离要大于等于半径之和。

d = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2))
d >= r1 + r2
为了避免sqrt后影响精度,故两边都开平方
d*d >= (r1 + r2)*(r1 + r2)
即(x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) >= (r1 + r2)*(r1 + r2)

4.如果两个圆相交或相切,我们可以就把它们视为一体,这样就构成了一个连通块,判断连通块是否满足上面四个条件。至于如何判断,就是判断连通块中的每个圆是否触及边界,具体用下列式子来判断。

x - r <= 0	-->	触及左边界  
x + r >= m	-->	触及右边界
y - r <= 0	-->	触及下边界
y + r >= n	-->	触及上边界

5.好了,现在知道怎么判断是否触及边界了,那么就需要想一下怎么知道连通块中包含哪些圆呢?这里我们可以借助图论的相关知识。就是如果两个圆有接触,就在这两个圆之间建立一条连接,我们可以把这个圆抽象成一个节点,这就变成了在两个节点之间建立一条无向边,这个连通块就成了一个图。遍历这个图即可知道这个连通块包含哪些圆。

6.大致的实现思路有了,现在我们来看如何用代码实现。

C++代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 2e6 + 10;   //注意M要取到N*N,原因是其中一个圆可能和其他所有圆都相交或相切
int m, n, k;
struct Sensor{
    int x, y, s;
}sen[N];
int h[N], e[M], ne[M], idx;
bool st[5];         //0,1,2,3分别代表上下左右四个边界是否接触
bool vis[N];        //该圆是否被访问过
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
//判断两圆是否相交或相切
bool check(Sensor a, Sensor b)
{
    if((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) <= (a.s + b.s) * (a.s + b.s)) return true;
    return false;
}
void dfs(int u)
{
    vis[u] = true;
    int x = sen[u].x, y = sen[u].y, s = sen[u].s;
    if(x - s <= 0) st[2] = true;
    if(x + s >= m) st[3] = true;
    if(y - s <= 0) st[1] = true;
    if(y + s >= n) st[0] = true;
    //遍历与该圆连通的圆
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!vis[j])
            dfs(j);
    }
}
int main()
{
    cin >> m >> n >> k;
    memset(h, -1, sizeof h);
    for(int i = 0; i < k; i++)
        cin >> sen[i].x >> sen[i].y >> sen[i].s;
    for(int i = 0; i < k; i++)
        for(int j = i + 1;j < k; j++)
        {
            if(check(sen[i], sen[j]))
            {
                add(i, j);
                add(j, i);
            }
        }
    bool flag = false;
    for(int i = 0; i < k; i++)
    {
        if(flag) break;
        if(vis[i]) continue;
        memset(st, 0, sizeof st);
        dfs(i);
        if((st[0] || st[2]) && (st[1] || st[3]))
            flag = true;
    }
    if(flag)
        puts("N");
    else
        puts("S");
}

此代码中使用的用邻接表建立图来源于yxc大佬的模板 解题思路来源

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 快速幂和矩阵快速幂(待进一步补充)

    它可以快速求出斐波那契数列,这里以一个题为例,Fibonacci POJ - 3070

    _DIY
  • 【Bit String Reordering UVALive - 6832 】【模拟】

    题目讲的主要是给你一个01串,然后给你要变成的01串格式,问你要转换成这一格式最少需要移动的步数。 题目不难,但当时并没有AC,3个小时的个人赛1道没AC,归...

    _DIY
  • 生成1~n的排列(模板),生成可重集的排列(对应紫书P184, P185)

    _DIY
  • 猎杀埃博拉病毒的算法

    大数据文摘
  • java基础02

    待你如初见
  • 微信小程序:为了满足三方需求,我们一直在改变

    小程序:我们正在加快开发速度,争取满足用户的需求。 “小程序升级实时音视频录制及播放能力,开放 Wi-Fi、NFC(HCE) 等硬件连接功能。同时提供按需加载、...

    企鹅号小编
  • Juicer实战详解

    Juicer软件的运行是非常简单的,只需要设置几个参数就可以了,本文利用官网的小的测试测试数据集来展示该软件的基本用法。

    生信修炼手册
  • java开发系统内核:创建文件操作API

    望月从良
  • Tree - 100. Same Tree

    Given two binary trees, write a function to check if they are the same or not.

    用户5705150
  • 小程序为何这么火?

    自小程序推出一年多以来,小程序已上线数量已经超过58万个,小程序数量还有逐渐增长的趋势。

    微宝阁

扫码关注云+社区

领取腾讯云代金券