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$ – Inuyasha Yagami Jan 21 at 12:23
  • $\begingroup$ @Inuyashayagami Just the number of all possible paths. $\endgroup$ – Exzone Jan 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$ – Inuyasha Yagami Jan 22 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$ – Inuyasha Yagami Jan 22 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$ – Inuyasha Yagami Jan 22 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$ – Inuyasha Yagami Jan 22 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$ – Inuyasha Yagami Jan 22 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.