2101. 引爆最多的炸弹

发表于2024-07-22更新于2024-08-17字数统计1.5k阅读时长14分阅读次数

摘要
Title: 2101. 引爆最多的炸弹
Categories: floyd fill

Powered by:NEFU AB-IN

Link

2101. 引爆最多的炸弹

题意

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。

你需要选择引爆 一个 炸弹。当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。

思路

  1. dfs
    建图：n 个炸弹看成 n 个节点，如果炸弹 x 可以引爆炸弹 y，那么就连一条从节点 x 到节点 y 的有向边。右边的炸弹可以引爆左边的炸弹，但是左边的炸弹无法引爆右边的炸弹，所以是有向边，而不是无向边，不能用并查集。
    所以可以用 floyd fill 去 dfs 含有向边的图
    注意！
    之前 floyd fill dfs 无向边的图去求连通块时，只用初始化一次 vis （状态数组），因为如果进入一个点，那么这个点的所有联通的点全部会被访问
    但是有向边的图不同，进入一个点，可能他只有入度的边，无出度的边，导致打上标记了，而别的点dfs不到它，所以每次需要情况 vis 数组

  2. floyd
    如果只关心点的是否到达性，那么可以用位运算优化floyd
    定义 f[i] 表示 i 可以到达的节点集合。注意 i 一定在 f[i] 中。
    如果 i 可以到达 k，那么 k 能到达的点，i 也可以到达，于是 i 能到达的点就是 f[i] 和 f[k] 的并集
    答案：所有 f[i] 集合大小的最大值。

代码

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
'''
Author: NEFU AB-IN
Date: 2024-07-22 19:30:24
FilePath: \LeetCode\2101\2101.py
LastEditTime: 2024-07-22 20:12:57
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def maximumDetonation(self, bombs) -> int:

        def check(bomb_x, bomb_y):
            _, x1, y1, r1 = bomb_x
            _, x2, y2, r2 = bomb_y
            dist = hypot(x2 - x1, y2 - y1)
            return dist <= r1

        n = len(bombs)
        g = Arr.graph(n)
        bombs = [(i, *bomb) for i, bomb in enumerate(bombs)]
        for bomb_x, bomb_y in permutations(bombs, 2):
            if check(bomb_x, bomb_y):
                g[bomb_x[0]].append(bomb_y[0])

        def dfs(u):
            nonlocal cnt
            vis[u] = True
            for v in g[u]:
                if not vis[v]:
                    cnt += 1
                    dfs(v)

        max_ = 1
        for i in range(n):
            cnt = 1
            vis = Arr.array(False, n)
            dfs(i)
            max_ = Math.max(max_, cnt)
        return max_
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
'''
Author: NEFU AB-IN
Date: 2024-07-22 19:30:24
FilePath: \LeetCode\2101\2101.py
LastEditTime: 2024-07-23 10:22:15
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    class GraphShortestPath:
        def __init__(self, n: int):
            self.n = n
            self.g = Arr.graph(n)
            self.spfa_cache = {}
            self.dijkstra_cache = {}
            self.floyd_cache = None

        def add_edge(self, u: int, v: int, w: int):
            """Add an edge to the graph."""
            self.g[u].append((v, w))

        def floyd_01(self) -> List[int]:
            """Floyd's algorithm for finding reachability between all pairs of nodes using bitwise operations."""
            n = self.n
            # Initialize reachability bitsets
            f = Arr.array(0, n)
            for u in range(n):
                f[u] |= 1 << u  # Each node can reach itself
                for v, w in self.g[u]:
                    f[u] |= 1 << v  # Add reachable nodes based on edges

            # Floyd-Warshall algorithm for reachability
            for k in range(n):
                for i in range(n):
                    if f[i] >> k & 1:  # If i can reach k
                        f[i] |= f[k]  # Then i can also reach all nodes k can reach

            return f


class Bit(int):
    def __new__(cls, value):
        return super(Bit, cls).__new__(cls, value)

    def __init__(self, value):
        self.bin_rep = bin(value)[2:]

    def bit_length(self): return len(self.bin_rep)
    def bit_count(self): return self.bin_rep.count('1')
    def lowest1(self): return Bit(self & -self)
    def lowest0(self): return Bit(~self & (self + 1))
    def clear_lowest1(self): return Bit(self & (self - 1))
    def clear_lowest0(self): return Bit(self | (self + 1))
    def get_bits(self, start, end): return self & Bit.range_mask(start, end)

    all_ones_mask = staticmethod(lambda length: (1 << length) - 1)
    all_zeros_mask = staticmethod(lambda length: 0)
    single_bit_mask = staticmethod(lambda position: 1 << position)
    range_mask = staticmethod(lambda start, end: ((1 << (end - start + 1)) - 1) << start)

# ————————————————————— Division line ——————————————————————
class Solution:
    def maximumDetonation(self, bombs) -> int:
        def check(bomb_x, bomb_y):
            _, x1, y1, r1 = bomb_x
            _, x2, y2, r2 = bomb_y
            dist = hypot(x2 - x1, y2 - y1)
            return dist <= r1

        n = len(bombs)
        g = Std.GraphShortestPath(n)
        bombs = [(i, *bomb) for i, bomb in enumerate(bombs)]
        for bomb_x, bomb_y in permutations(bombs, 2):
            if check(bomb_x, bomb_y):
                g.add_edge(bomb_x[0], bomb_y[0], 0)

        dist = g.floyd_01()
        return max(Bit(s).bit_count() for s in dist)

使用搜索：谷歌必应百度