# Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions

I've been given a matrix path problem to solve and I need some hints / advises. You're given a $$m \times n$$ matrix where $$m$$ is number of rows and $$n$$ number of columns. When you're in a cell $$(i,j)$$ you can only move to cells $$(i,j+1)$$, $$(i-1,j+1)$$ and $$(i+1,j+1)$$. Three subproblems have to be solved. I solved first two and I'm stuck solving the third one now.

First one is to find all possible paths from $$(0,0)$$ to $$(0,n-1)$$, second one is to find all paths with given obstacles. The third one is kind of tricky. You're given a vector of must visited rows while traversing (they don't have to be sorted). For example: if you're given a vector $$[ r_2,r_1]$$, you have to find all possible ways to reach row 2, then all possible ways to visit row 1 after visiting row 2 and finally all paths to come to cell $$(0,n-1)$$ with given restrictions.

Any advises or hints for this one?

• You want to output the "number of possible paths" or print "all possible paths"? – Inuyasha Yagami Jan 21 at 12:23
• @Inuyashayagami Just the number of all possible paths. – Exzone Jan 21 at 12:27

Subproblem 1: Find the number of possible paths from $$[i,j]$$ to $$[k,\ell]$$ for all $$i,k \in \{0,\dotsc,m-1\}$$ and $$j,k \in \{0,\dotsc,n-1\}$$. Store them in a table $$A$$ of size $$m$$ x $$n$$ x $$m$$ x $$n$$. In other words, an entry $$A[i][j][k][\ell]$$ stores the number of possible paths from $$[i,j]$$ to $$[k,\ell]$$. You can construct this table since this is similar to the second variant of your problem while considering the restrictions.

Subproblem 2: Find the number of possible paths from $$[i,j]$$ to $$[k,\ell]$$ that does not goes through the entries: $$[k,0], \dotsc, [k,\ell-1]$$, for all $$i,k \in \{0,\dotsc,m-1\}$$ and $$j,k \in \{0,\dotsc,n-1\}$$. Store them in a table $$T$$ of size $$m$$ x $$n$$ x $$m$$ x $$n$$. In other words, an entry $$T[i][j][k][\ell]$$ stores the number of possible paths from $$[i,j]$$ to $$[k,\ell]$$ that does not pass through the entries: $$[k,0], \dotsc,[k,\ell-1]$$. You can construct this table from the entries of the previous table $$A$$ but it will require some more work.

Main Problem: Suppose the row vector is $$(r_{i_{1}},r_{i_{2}},\dotsc,r_{i_{p}})$$. Here, I am assuming the $$0$$ based indexing. In other words, if $$r_{i_{j}} = 4$$, it means it is the fifth row. For sake of better understanding of the solution, let me add $$r_{i_{0}} = 0$$ at the beginning of this row vector. Now, the row vector is $$(r_{i_{0}},r_{i_{1}},r_{i_{2}},\dotsc,r_{i_{p}})$$.

Now, we define a table $$R$$ of size $$(p+1)$$ x $$n$$ such that $$R[t][j]$$ denote the number of possible paths from $$[r_{i_{t}},j]$$ (for valid $$r_{i_{t}}$$ and $$j$$) to the $$[0,n-1]$$ that goes through the row vector $$(r_{i_{t+1}},\dotsc,r_{i_{p}})$$

Output: The algorithm should output $$R[0][0]$$ since it denote the number of possible paths from $$[0,0]$$ to the $$[0,n-1]$$ that goes through the row vector $$(r_{i_{1}},\dotsc,r_{i_{p}})$$

Induction Step:

$$R[t][j] = \sum_{\ell = 0}^{\ell = n-1} \Big( T[r_{i_{t}}][j][r_{i_{t+1}}][\ell] \Big)\cdot \Big(R[t+1][\ell] \Big)$$

Base Step: When $$t$$ becomes equal to $$p$$, we get $$R[p][j]$$, which denote the number of possible paths from $$[r_{i_{p}},j]$$ to $$[0,n-1]$$ that does not goes through any row vector.

$$R[p][j] = A[r_{i_{p}}][j][0][n-1] \quad \textrm{ for all valid j \in \{0,\dotsc,n-1\}}$$

Since you just asked for hints, this is more than sufficient.

• @Exzone Yes, you can go to $r_{4}$ and rows below which are valid. This fact is captured by the base step $R[p][j]$, which defines all possible paths from $[r_{3}][j]$ to reach to $[0][n-1]$. These paths might go through the rows which lie below $r_{3}$. – Inuyasha Yagami Jan 22 at 13:44
• @Exzone Note that $T[i][j][k][l]$ captures all the paths between $[i][j]$ and $[k][\ell]$ without taking into account any "row vector restrictions". We use this fact repeatedly in the induction step and the base step. This allows the algorithm to go to any "row". – Inuyasha Yagami Jan 22 at 14:02
• @Exzone There were typos in my algorithm. For example, I was assuming that given matrix is of size $n$ x $n$. However, now I have made changes to the answer. Please check that again. – Inuyasha Yagami Jan 22 at 16:03
• @Exzone The matrix $R$ should be $(p+1)$ x $n$ only. Apologies for the confusion. I am thinking on better than $O(n^6)$ solution. – Inuyasha Yagami Jan 22 at 16:07
• @Exzone You can construct the matrix $T$ more efficiently using DP in $O(m^2 \cdot n^2)$ time. The remaining algorithm works in $O(p \cdot n^2)$ time. So the overall time would be $O(m^2 n^2)$. Try constructing $T$ efficiently. – Inuyasha Yagami Jan 22 at 16:16