Building maze to maximize shortest path, may be given waypoints and teleports
Just a note: even the simpler version without waypoints and teleports is NP-hard:
Start with a maze in which the dots mimic the edges of a grid graph $G$ of max degree 3,  and $X$s are placed &quot;around&quot; them (the dots are &quot;corridors&quot;). Put the $O$ in a corner and the $F$ near it with a dot in the middle.
Maximizing the shortest path (adding more Xs) is equivalent to finding an Hamiltonian path in the original graph $G$ which is NP-complete (each new $X$ must block a &quot;corridor&quot;, i.e. it removes an edge of $G$).