# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

In this problem you will have to solve a puzzle game named “Pipeline”. 90’s kids knows this game very well.

In this game on each level there is an underground Grid with **r** rows and **c** columns. There is a source cell (**x _{1}**,

These pipes can be rotated at 90 degree any number of times. You will have to connect these pipes

You can use pipes

As this game is too easy, the developer made some changes in the game. On each level you will have to answer how many ways are there to solve this puzzle. For the example above the grid size is (6, 6), source (1, 2), destination(4, 3) and Given 7 pipes: 2, 1, 1, 1, 2, 2, 2. With these pipes you can solve this puzzle in this 2 ways that are given above.

In the first line you will be given **T (1 ≤ T ≤ 100)** - the number of levels you will have to play.

On each level :

1. The first line will contain **r**, **c**, **n** **(1 < r, c ≤ 10) (0 < n ≤ 20)** - grid size(r,c) and number of pipes(n).

2. The second line will contain **n** space separated integers **p[1,2,…n]** - the type( **1** or **2**) of the pipe.

3. The third line will contain **x _{1}**,

For each level, output the number of ways you can solve this level on each line.

Input | Output |
---|---|

2 5 5 7 2 1 1 1 2 2 2 1 2 4 3 3 3 4 2 2 1 2 2 2 2 3 | 2 5 |

Pipes don’t need to enter into the destination cell, It just needs to reach it. You can not place any pipe in the destination cell.

33% Solution Ratio

Riaz_BSMRSTUEarliest,

Riaz_BSMRSTUFastest, 0.0s

BrehamPieLightest, 131 kB

Riaz_BSMRSTUShortest, 2945B

Login to submit