Come Back Home
InterviewTime limit2sMemory limit128 MB
Count simple paths of exact length K from the bottom-left to the top-right cell of a small grid, avoiding blocked cells and revisits.
- Level
Easy3 of 10
- Topics
- Backtracking, DFS, Matrix
- Solved
- No attempts yet
Problem
Hansu is returning home after camp. He starts in the lower-left cell of the map, and his home is in the upper-right cell. He never visits the same cell twice, and cells marked T cannot be entered.
Given an R x C grid and an integer K, count the number of simple paths from the start cell to the home cell whose length is exactly K. The length of a path is the number of visited cells, including both the start cell and the home cell.
Input
The first line contains three integers R (1 <= R <= 5), C (1 <= C <= 5), and K (1 <= K <= R x C).
Each of the next R lines contains a string of length C describing the map. A . cell can be entered, and a T cell cannot be entered.
Output
Print the number of ways to reach home with distance K.