Two Random Walks

Observe that the first move of A doesn't affect anything; we can rotate the grid so A moves to the right, and all the distances remain equal. In addition, A and B don't interact with each other, so let's as well put A and B on the same starting point, $(1,0)$ , moving two steps randomly.

image

It can be verified that the numbers in red, green, and blue above are the number of ways to get to that node with exactly two steps; all other nodes have zero ways to reach in exactly two steps from the central red node. From here, we can also observe that there are three distinct distances: $\sqrt{1}$ (pink), having $9$ ways to arrive there; $\sqrt{5}$ (orange), having $6$ ways to arrive there; $\sqrt{9}$ (purple), having $1$ way to arrive there. Note that there are $16$ ways in total, so the probability for each distance is simply the number of ways to arrive with that distance divided by $16$ .

Thus the rest is immediate. For each distance, compute the probability that B arrives to that distance and multiply it with the probability that A arrives to that distance or more.

$P = \frac{9}{16} \cdot \left( \frac{9+6+1}{16} \right) + \frac{6}{16} \cdot \left( \frac{6+1}{16} \right) + \frac{1}{16} \cdot \frac{1}{16}$

$= \frac{9 \cdot 16 + 6 \cdot 7 + 1 \cdot 1}{16 \cdot 16}$

$= \frac{187}{256}$

And so $p+q = 187+256 = \boxed{443}$ .