0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ You want to output the "number of possible paths" or print "all possible paths"? $\endgroup$ Jan 21 '21 at 12:23
  • $\begingroup$ @Inuyashayagami Just the number of all possible paths. $\endgroup$
    – Exzone
    Jan 21 '21 at 12:27
1
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ @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}$. $\endgroup$ Jan 22 '21 at 13:44
  • 1
    $\begingroup$ @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". $\endgroup$ Jan 22 '21 at 14:02
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 22 '21 at 16:03
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 22 '21 at 16:07
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 22 '21 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.