Hackerrank: Count Luck


Ron and Hermione are deep in the Forbidden Forest collecting potion ingredients, and they’ve managed to lose their way. The path out of the forest is blocked, so they must make their way to a portkey that will transport them back to Hogwarts.

Consider the forest as an grid. Each cell is either empty (represented by .) or blocked by a tree (represented by ). Ron and Hermione can move (together inside a single cell) LEFT, RIGHT, UP, and DOWNthrough empty cells, but they cannot travel through a tree cell. Their starting cell is marked with the character , and the cell with the portkey is marked with a . The upper-left corner is indexed as .

In example above, Ron and Hermione are located at index and the portkey is at . Each cell is indexed according to Matrix Conventions

Hermione decides it’s time to find the portkey and leave. Each time they are able to move in more than one direction, she waves her wand and it points to the correct direction. Ron is betting that she will have to wave her wand exactly times. Can you determine if Ron’s guesses are correct?

Note: It is guaranteed that there is only one path from the starting location to the portkey.

Input Format

The first line contains an integer, , the number of test cases.

Each test case is described as follows:
The first line contains space-separated integers, and , respectively, denoting the forest matrix.
The subsequent lines each contain a string of length describing a row of the forest matrix.
The last line contains an integer, , denoting Ron’s guess as to how many times Hermione will wave her wand.


  • There will be exactly one and one in the forest.
  • Exactly one path exists between and .

Output Format

On a new line for each test case, print if Ron impresses Hermione by guessing correctly; otherwise, print .

Sample Input

Sample Output


For each test case , denotes the number of times Hermione waves her wand.

Case 0: Hermione waves her wand at , giving us . Because , we print on a new line.
Case 1: Hermione waves her wand at , , and , giving us . Because , we print on a new line.
Case 2: Hermione waves her wand at , , and , giving us . Because and , and we print on a new line.

这个题是个深搜,只不过需要在途中数valid的neighbor的个数。需要注意的细节是:1. 起始位置没有设为’X’而是’M’,在开始搜索的时候也没有改变其值,因此在isValid函数中需要加一个判断是否是’M’,或者就直接在开始的时候将其改为’X’;2. 只有在valid的path中的岔路口才计入最后的count中。