@@jakubgwozdz2780 BFS is O(N), and in this particular case, N~=length of the last path before its blocked, i.e. around 500. Sure it also needs to check a bunch of removed blocks (~1000) but mostly doesn't need to do anything about them. With UF you either join all the available spaces and go backwards, processing ~3000 union operations (free blocks at the end+removed blocks until start and end are joined), or join blocks and go forward, also processing around ~3000 unions until the corner sets are joined. Even if UF was O(1) it would stil lbe slower here, and with that extra log* it's much slower.
th-cam.com/users/shortsoAWJLoBlmuU - part 2 without any path finding
yeah, tested that approach as well. Visually interesting, but slower than backwards BFS.
@ really? I’d say union-find on preallocated array is as fast as possible, most def faster than bfs, but maybe I don’t see something here…
@@jakubgwozdz2780 BFS is O(N), and in this particular case, N~=length of the last path before its blocked, i.e. around 500. Sure it also needs to check a bunch of removed blocks (~1000) but mostly doesn't need to do anything about them. With UF you either join all the available spaces and go backwards, processing ~3000 union operations (free blocks at the end+removed blocks until start and end are joined), or join blocks and go forward, also processing around ~3000 unions until the corner sets are joined. Even if UF was O(1) it would stil lbe slower here, and with that extra log* it's much slower.
@@jakubgwozdz2780 in practical terms, my part1 takes ~14 us (single BFS but with still lots of points available), and part2 BFS takes ~4 us.