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.

Task

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 (10⁹ + 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.