A cat walk

Without restriction, there are $\left( \begin{matrix} 18 \\ 9 \end{matrix} \right)=48620$ ways of walking Sakamoto-san.

Denote as $A$ the upper left dog spot, as $B$ the upper right dog spot, as $C$ the lower left dog spot, and as $D$ the lower right dog spot.

We will use the Principle of Inclusion-Exclusion to enumerate the number of routes passing through the dog spot(s) before taking the complement of it.

Let $N(X)$ denotes the number of ways to complete the route walking through dog spot $X$ , while $N(X \cap Y)$ denotes the number of ways to complete the route walking through both dog spots $X$ and $Y$ , with $X,Y \in \{A,B,C,D\}$ .

In other words, we are trying to evaluate $N(A \cup B \cup C \cup D)= N(A)+N(B)+N(C)+N(D)-N(A \cap B)-N(A \cap C)-N(A \cap D)-N(B \cap C)-N(B \cap D)-N(C \cap D)+N(A \cap B \cap C)+N(A \cap B \cap D)+N(A \cap C \cap D)+N(B \cap C \cap D)-N(A \cap B \cap C \cap D)$ .

Verify the following:

$N(A)= \left( \begin{matrix} 9 \\ 3 \end{matrix} \right)\left( \begin{matrix} 9 \\ 3 \end{matrix} \right)=7056$

$N(B)=\left( \begin{matrix} 12 \\ 6 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=18480$

$N(C)=\left( \begin{matrix} 12 \\ 6 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=18480$

$N(D)=\left( \begin{matrix} 9 \\ 3 \end{matrix} \right)\left( \begin{matrix} 9 \\ 3 \end{matrix} \right)=7056$

$N(A \cap B)=\left( \begin{matrix} 9 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=1680$

$N(A \cap C)=\left( \begin{matrix} 9 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=1680$

$N(A \cap D)=0$

$N(B \cap C)=\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=8000$

$N(B \cap D)=\left( \begin{matrix} 9 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=1680$

$N(C \cap D)=\left( \begin{matrix} 9 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=1680$

$N(A \cap B \cap C)=\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=400$

$N(A \cap B \cap D)=0$

$N(A \cap C \cap D)=0$

$N(B \cap C \cap D)=\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)\left( \begin{matrix} 6 \\ 3 \end{matrix} \right)=400$

$N(A \cap B \cap C \cap D)=0$

Therefore, we have

$N(A \cup B \cup C \cup D)=18480(2)+7056(2)-1680(4)-8000+400(2)=37152$

Taking the complement yields the answer.

$48620-37152=\boxed{11468}$

Solution:

Movement can be written using letters R and U . They will go exactly 9 times up and 9 times right. Therefore, there are $48620$ different ways from start to finish point. Now, we will subtract every way that passes through dog spot, but we have to be careful, to avoid including some ways twice.

Passing through first dog spot (3, 3), there are $\left( \begin{matrix} 6 \\ 3 \end{matrix} \right) \left( \begin{matrix} 12 \\ 6 \end{matrix} \right) = 18480$ ways in total.

Passing through the second (or third) dog sport (3, 6) or (6, 3), there are $\left( \begin{matrix} 9 \\ 6 \end{matrix} \right) \left( \begin{matrix} 9 \\ 6 \end{matrix} \right)$ , but $20 \times \left( \begin{matrix} 9 \\ 6 \end{matrix} \right)$ are already included when passing through the firs dog spot. When that is subtracted, there will be $5376$ new ways, that are not included until now.

Passing through the fourth (6, 6) dog spot. We will proceed similarly as for the third and the second one. Calculate all the ways that pass through 4th spot, then subtract those who pass through 4th and nth spot (n = 1, 2, 3). Leaving $7920$ .

When they are all subtracted from the all possible ways, $\boxed{11468}$ safe ways are left.