Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
302 views
in Technique[技术] by (71.8m points)

c++ - What is the fastest algorithm for this distance problem ? (Thirsty Person)

I have a bunch of cities (orange) and streets (green), and the problem to solve is to know the worst point on the street where you can be where you have the maximum distance to ANY city. All the streets are rectangular (90°)

My approach is to fill every city to any direction with increasing numbers, for example "1" around every city on any street, then "2" , until you hit another number and stop. After all recursions are stopped, take the max.

However, I have to do it around a billion times, so any ideas to improve it are welcome.

My aborted idea: if I kick out some cities that are close to each other, I lose the stop for the rest of the recursion.

This is an example map where J10 is the worst place where you can be if you are thirsty.. example

question from:https://stackoverflow.com/questions/65908767/what-is-the-fastest-algorithm-for-this-distance-problem-thirsty-person

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Depending on how regular the streets are you could do the following

Make a distance map from all cities then sort the squares so that the furthest from any city is in front, then check from the front if there is a street.

// Setup 
clear map
for all cities
  set distance to zero
  add to queue

while queue
  pop square
  for all neighbour squares
    if unvisited 
      set distance to squares plus one
      add neighbour squares to queue

Sort squares after decreasing distance 

CheckDistance
  for all sorted squares from furthest distance.
    Check if street
      return value

This will not work if any road serpentines.

This should give a reduced time if streets are common.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...