HMMT 2022 U24

Let $S_{0}$ be a unit square in the Cartesian plane with horizontal and vertical sides. For any $n>0$, the shape $S_{n}$ is formed by adjoining 9 copies of $S_{n-1}$ in a $3 \times 3$ grid, and then removing the center copy. For example, $S_{3}$ is shown below:

Let $a_{n}$ be the expected value of $\left|x-x^{\prime}\right|+\left|y-y^{\prime}\right|$, where $(x, y)$ and $\left(x^{\prime}, y^{\prime}\right)$ are two points chosen randomly within $S_{n}$. There exist relatively prime positive integers $a$ and $b$ such that

$$\lim _{n \rightarrow \infty} \frac{a_{n}}{3^{n}}=\frac{a}{b} .$$

Compute $100 a+b$.