If we go $UP$ we will follow paths $\in [0, 4)$, there is no paths to $RIGHT$, if we go $DOWN$ we will follow paths $\in [4, 4+9)$, so we need to go $DOWN$ and choose $(7 - 4)th$ path among all that starts in that cell. More intuitively, imagine we at $X$ cell choosing for $7th$ path: \\ \hspace L \in [Count_u + Count_l + Count_d, A)\\Īnd $Count_u$ means how many paths of length $K$ starts at $(R_c, C_c)$ and ends at $(R_e, C_e)$ and first move is $UP$, $Count_l$, $Count_d$, $Count_r$ defines respectively for another directions. \langle RIGHT, choose(R_c, C_c + 1, L - Count_u, K - 1)\rangle,
\langle UP, choose(R_c - 1, C_c, L - 0, K - 1)\rangle, Let $choose(R_c, C_c, L, K)$ - function that return $Lth$ path of length $K$ staring at cell $(R_c, C_c)$ and ending at $E(R_e, C_e)$: We had ordered all $A$ paths and choose some path to output $L$ ($0-indexed$) and just need to find it. Then we know how many paths of length $K$ exist between cells $S$ and $E$, lets name it $A=dp$, now we can uniformly at random peek number $L\in[0, A)$ that will identify choosen path among all $A$ available. if $K>0$ let's suppose: Paths that go UP $if $K=0$ we have $0$ or $1$ such paths (such collection is always ordered).Now add order relation between all paths of length $K$ starting at cell $(R, C)$ and ending at cell $E(R_e, C_e)$: count how many paths of length $K$ exist that start at $(R_e, C_e)$) and save all step of dynamic (we will use it in next steps). Generate random path of length $K$ between cells $S(R_s, C_s)$ and $E(R_e, C_e)$.įirst of all we need count how many paths of length $K$ exists between this cells, for that we can use previously described dynamic:įuthermore run it from end cell (e.g.
This will take $O(N*M*K)$ time, where $N$ - number of rows, $M$ - number of columns, and $O(N*M*K)$ memory if we will keep all steps of dynamic or $O(N*M)$ if we will keep only last step of dynamic. $X N$ or $Y N$)Īlso we can even add more constraints for problem and add obstacles: for doing so - we need to suppose $dp=0, \forall K$, where cell $(R, C)$ is impassable (e.g. Here we suppose $dp=0$, for any $X$ and $Y$ that outside of grid (e.g. How many paths of length $K$ exists that start in $(StartRow, StartColumn)$ and ends in $(R, C)$".ĭp = dp + dp + dp + dp Such problem can be solved by dynamic programming: let $dp$ be answer for question: How many paths of length $K$ exists starting at coordinate $(StartRow, StartColumn)$. Algo for solving problem when path self-intersections are allowed Auxiliary problem
0 kommentar(er)
