Nontrivial Hamiltonian Cycle on 2D grid.

Revision en2, by Soul_Full_Of_Thunder, 2020-07-05 23:41:10

Two days ago, one of my friends (Danylo99) told me about a cool problem from a recent SIT contest. The goal was to find a nontrivial cycle that visits all cells on a 2D grid with even sides.

I thought it would be interesting to visualize the results.

Here is a slightly larger one. If anyone knows other approaches, please share :)

By the way, I also made a video of what's going on inside the algorithm.

Hope you all have a great day!

Tags #hamiltonian-circuit, minimum spanning tree, #constructive algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Soul_Full_Of_Thunder 2020-07-06 08:57:51 70 Tiny change: 'ay! \n\n\n ' -> 'ay! \n\n\n![ ](https://codeforces.net/156f31/result.png)'
en2 English Soul_Full_Of_Thunder 2020-07-05 23:41:10 2 Tiny change: ' a recent CIT contest' -> ' a recent SIT contest'
en1 English Soul_Full_Of_Thunder 2020-07-05 23:36:05 715 Initial revision (published)