离散化

离散化用于值域（值的范围）较大，但是查询数据范围较小的情况

1. 将所有元素添加到集合中（去重）

2. 排序

3. 映射

4. 查询

当然1，2步骤也可以先将元素都添加的列表中然后再去重

逃离大迷宫

1036. 逃离大迷宫

from typing import List
from bisect import insort, bisect_left
from collections import deque

MOVE = {(1, 0), (0, 1), (-1, 0), (0, -1)}


class Solution:

    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:

        if not blocked:
            return True

        x_all_nums = [0, source[0], 999999]
        y_all_nums = [0, source[1], 999999]
        for x, y in blocked:
            insort(x_all_nums, x)
            insort(y_all_nums, y)
        insort(x_all_nums, target[0])
        insort(y_all_nums, target[1])

        x_all_nums = self.unique(x_all_nums)
        y_all_nums = self.unique(y_all_nums)

        ns = (bisect_left(x_all_nums, source[0]), bisect_left(y_all_nums, source[1]))
        nt = (bisect_left(x_all_nums, target[0]), bisect_left(y_all_nums, target[1]))
        nbs = {(bisect_left(x_all_nums, x), bisect_left(y_all_nums, y)) for x, y in blocked}

        dq = deque()
        dq.append(ns)
        mark = {ns, }
        while dq:
            a, b = dq.popleft()
            for x, y in MOVE:
                x += a
                y += b
                if not (0 <= x < len(x_all_nums) and 0 <= y < len(y_all_nums)) or (x, y) in mark or (x, y) in nbs:
                    continue

                if x == nt[0] and y == nt[1]:
                    return True
                dq.append((x, y))
                mark.add((x, y))
        return False

    def unique(self, nums):
        if not nums:
            return nums
        ans = [nums[0]]
        for num in nums[1:]:
            if num != ans[-1]:
                ans.append(num)
        return ans

求区域的个数

《挑战程序设计竞赛》的 3.2.5 节

坐标离散化.png

样例输入

坐标离散化-样例输入.png

离散化结果

坐标离散化-示例.png

离散化实现

表示不理解6n*6n，对于所给样例是将10*10的格子通过离散化映射为6*6，难道作者想表达的是6*6？而非6n*6n?（毕竟在样例中n=5，那么将10*10映射到30*30有点不符合逻辑） 下面我对所有元素进行离散化得到的是7*7的矩阵

from bisect import insort, bisect_left

w_min = h_min = 1
# w_max = h_max = 1000000

w_max, h_max, n = [int(c) for c in input().split(" ")]
x1 = [int(c) for c in input().split(" ")]
x2 = [int(c) for c in input().split(" ")]
y1 = [int(c) for c in input().split(" ")]
y2 = [int(c) for c in input().split(" ")]

all_nums = [w_min, h_min, w_max, h_max]
for i in range(n):
    insort(all_nums, x1[i])
    insort(all_nums, x2[i])
    insort(all_nums, y1[i])
    insort(all_nums, y2[i])


def unique(nums):
    if not nums:
        return nums
    ans = [nums[0]]
    for num in nums[1:]:
        if num != ans[-1]:
            ans.append(num)
    return ans


def conv(nums: list, d: list) -> list:
    return [bisect_left(d, num) for num in nums]


all_nums = unique(all_nums)
print("x1: ", conv(x1, all_nums))
print("x2: ", conv(x2, all_nums))
print("y1: ", conv(y1, all_nums))
print("y2: ", conv(y2, all_nums))

"""
IN:
10 10 5
1 1 4 9 10
6 10 4 9 10
4 8 1 1 6
4 8 10 5 10

注意这里离散化之后下标从0开始
OUT:
x1:  [0, 0, 1, 5, 6]
x2:  [3, 6, 1, 5, 6]
y1:  [1, 4, 0, 0, 3]
y2:  [1, 4, 6, 2, 6]
"""