# Sherlock and the Maze – HackerRank Solution

In this post, we will solve Sherlock and the Maze HackerRank Solution. This problem (Sherlock and the Maze) is a part of HackerRank Functional Programming series.

Watson gives a 2-D grid to Sherlock. Rows are numbered 1 to N from top to bottom and columns are numbered 1 to M from left to right. Sherlock is at position (1,1) right now and he is free to face any direction before he starts to move. He needs to reach (N,M). In one step, he can either move downwards or rightwards. Also, he cannot make more than K turns during his whole journey.

There are two possible scenarios when a turn can occur at pointÂ (i, j):

``````Turns Right: (i-1, j)  ->  (i, j)  ->  (i, j+1)
Down        Right

Turns Down:  (i, j-1)  ->  (i, j)  ->  (i+1, j)
Right        Dowm``````

GivenÂ N,Â MÂ andÂ K, help him by printing the number of ways to reachÂ (N,M)Â with at mostÂ KÂ turns. As this value can be very large, print the answer modulo (109Â + 7).

## Input

First line containsÂ T, the number of testcases. ThenÂ TÂ lines follow, where each line represents a test case. Each testcase consists of three space separated integers,Â N M K, whereÂ (N, M)Â is the final location andÂ KÂ is the maximum number of allowed turns.

## Output

For each testcase, print the required answer in one line.

## Constraints

• 1 â‰¤Â TÂ â‰¤ 10
• 1 â‰¤Â N, MÂ â‰¤ 100
• 0 â‰¤Â KÂ â‰¤ 100

Note

1. He can takeÂ at mostÂ KÂ turns.
2. He is free to face any direction before starting fromÂ (1, 1).

Sample Input

``````3
2 2 3
2 3 1
4 4 4``````

Sample Output

``````2
2
18``````

Explanation

Test Case #00:Â There is no way to reachÂ (2, 2)Â with 0, 2 or 3 turns. He will always reachÂ (2, 2)Â with 1 turn only. There are two ways shown below:

1. He starts from (1, 1) facing right and moves to (1, 2). Then he faces down and moves to (2, 2).
2. He starts from (1, 1) facing down and moves to (2, 1). Then he turns right and moves to (2, 2).

Test Case #01:Â He can’t reachÂ (2, 3)Â with 0 turns. There are only two ways to reachÂ (2, 3)Â with exactly 1 turn.

1. He starts from (1, 1) facing down and moves to (2, 1). Then he turns right and takes two steps forward to reach (2, 3).
2. He starts from (1, 1) facing right and moves two steps forward to reach (1, 3). Then he turns down and proceeds one step to (2, 3).

Test Case #02:Â There are 0 ways with 0 turn, 2 ways with 1 turn, 4 ways with 2 turns, 8 ways with 3 turns and 4 ways with 4 turns to reachÂ (4, 4).

## Solution – Sherlock and the Maze – HackerRank Solution

Scala

```import java.util.Scanner

import scala.collection.mutable

object Solution {
private val data = mutable.Map[(Int, Int, Int, Boolean), Int]()

def main(args: Array[String]): Unit = {
val sc = new Scanner(System.in)

val t = sc.nextInt
(0 until t).foreach(_ => {
val n = sc.nextInt
val m = sc.nextInt
val k = sc.nextInt

println(solve(n, m, k))
})

sc.close()
}

def solve(m: Int, n: Int, k: Int): Int = {
val modulo = 1000000007

def inner(m: Int, n: Int, k: Int, isRight: Boolean): Int = {
val (m1, n1, isRight1) = if (m < n) (m, n, isRight) else (n, m, !isRight)

data.getOrElseUpdate((m1, n1, k, isRight1), {
if (k < 0 || m1 < 1 || n1 < 1) 0
else if (m1 == 1 && n1 == 1) 1
else (inner(m1 - 1, n1, if (isRight1) k else k - 1, isRight = true) +
inner(m1, n1 - 1, if (!isRight1) k else k - 1, isRight = false)) % modulo
})
}

if (m == 1 && n == 1) 1 else (inner(m - 1, n, k, isRight = true) + inner(m, n - 1, k, isRight = false)) % modulo
}
}
```

Note: This problem (Sherlock and the Maze) is generated by HackerRank but the solutions is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.