Do not allow teleportation(traveling with CRs or village idol) if there aren't at least one free tile inside 5(for example) tile radius from the center of destination CR or idol. You can show message like "Destination is blocked".
I bet you are using spiral-like algorithm when looking for nearest free tile to the destination point, so you can set maximum radius for spirale for instance.
Thanks.