Mine runs in 27s too 😉
with bfs no optimization
here are examples of algorithms with reasonable sub-second times: https://old.reddit.com/r/adventofcode/comments/ec8090/2019_day_18_solutions/
thanks!