### PROBLEM LINK:

**Author:** Zi Song Yeoh

### DIFFICULTY:

EASY

### PREREQUISITES:

DYNAMIC PROGRAMMING

### PROBLEM:

Given a grid, find the number of ways a robot can reach each square after k moves.

### EXPLANATION:

To solve subtask 1, a simple exponential brute force suffice. There are 4^{10} \approx 10^{6} possible sequences of moves and thus we can try them all. This approach works in O(4^{k} \cdot k) time.

To get AC, we can use a simple dp solution. Let dp[i][j][k] be the number of ways to reach square (i, j) in k moves. Now, we can easily fill this dp table in O(nmk) time by checking the four neighbours each square. Time complexity is O(nmk).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.