= Solution
Write $F=|V|\le mn$. The ordered position pairs give at most $F^2$ states, or $F(F-1)$ live states after excluding capture. Thus the usual <Big O notation> estimate is \b[$O(m^2n^2)$]. An additional terminal-failure marker changes this by only one.
For $k$ distinguishable foxes, retain $(r,f_1,\ldots,f_k)$. Different foxes may share a square; none may share the rabbit's square in a live state. There are at most $F(F-1)^k$ live position tuples, giving \b[$O((mn)^{k+1})$]. These counts describe possible encodings; obstacles, starting positions and the fixed fox rule can make the reachable <state space> much smaller.
Back to article page
