Step 1: Separate the humans from all the four legged creatures.
Humans contribute $9 \times 2 = 18$ legs. Every other creature, lions and cubs, has exactly 4 legs, so it helps to count lions and cubs together and multiply by 4 only once at the end.
Step 2: Count lions and cubs as powers of 9.
Lions $= 9^3 = 729$ (one factor of 9 for humans, one for cages, one for lions per cage). Cubs $= 9^4 = 6561$ (one more factor of 9, since each lion has 9 cubs).
Step 3: Add lions and cubs, then multiply by 4 legs each.
Lions plus cubs $= 729 + 6561 = 7290$. Since each of these has 4 legs, their legs total $7290 \times 4 = 29160$.
Step 4: Add the human legs back in.
Total legs $= 18 + 29160 = 29178$, matching the first method.
Final Answer:
Total legs in the ship = 29178.
\[ \boxed{29178} \]