【acwing】528. cheese

subject

Ideas

Train of thought

One sentence question : You have to go from the lowest point to the highest point , You must start from the hole connecting with the lower boundary , And you can only walk to the cheese connected with your cheese every time .

For two cheeses , Their distance must be less than 2×r, Is considered to be interlinked .

Two points in space P1(x1,y1,z1)、P2(x2,y2,z2) The formula of distance is as follows ：

Conditions
The condition of this topic is : Connectivity & Distance formula between two points .
The nature of this topic : Or the connectivity mentioned above . That is, the two cheeses must be connected , Can be transferred

Algorithm to choose ： Let's have a preliminary look at this topic , Find it particularly cumbersome , However, in fact, this problem is a maze problem in plane rectangular coordinate system .
For the maze problem , obviously BFS Breadth first search is our best choice .

Analytic algorithm

First of all, for a search topic , We still have three basic goals

Goal one : Direction indicator array : For this topic , Obviously, every hole connected with it can , So the direction of this question indicates that the array is useless .

Goal two : Boundary treatment : For this topic , In fact, there are no requirements for our coordinates , Because connectivity already contains all the conditions .

Goal three : Expand the guidelines : Every search topic , The difficulty often lies in this expansion criterion , This topic is no exception , We found that , The expansion criterion of this topic is the connectivity in the topic , As long as the two points are connected , Then we can expand .

Train of thought two

Obvious , This problem is related to joint search

Let's look at the picture above , Do you see some doorways ？ We divide all holes into several sets , Once two cavities intersect or tangent , Just put them in the same set .

We can also draw 2 Special elements , Represent bottom and top respectively , If a cavity contacts the bottom , Then put it in the same set as the element representing the bottom , The same is true for the top . Last , Just see if the top and bottom are in the same set . This can be achieved by merging and searching sets .

Idea 1 code

Thought two code

Boss analysis