Honey Heist: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 Created page with "This problem asks us the number of steps taken to reach a given node on a hexagonal grid. It is trivially a BFS, but the challenge is that the grid is hexagonal. Fortunately,..." |
imported>Kmk21 No edit summary |
||
| Line 5: | Line 5: | ||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
[[Category:Mcpc2017]] | [[Category:Mcpc2017]] | ||
[[Category:Scusa2017]] | |||
[[Category:Algorithm Easy]] | [[Category:Algorithm Easy]] | ||
[[Category:Implementation Medium]] | [[Category:Implementation Medium]] | ||
[[Category:BFS]] | [[Category:BFS]] | ||
Latest revision as of 20:34, 29 December 2017
This problem asks us the number of steps taken to reach a given node on a hexagonal grid.
It is trivially a BFS, but the challenge is that the grid is hexagonal. Fortunately, given that each edge only has max 20 nodes, we can write some code up front to calculate which cells border which others. Then once we have a graph, it's literally a BFS and check the distance to the destination cell