Count Grid Paths Without Three Consecutive Moves

Question

Given a grid, the task is to count the number of unique paths from the top-left corner to the bottom-right corner without making three consecutive moves in the same direction.

Codemia · Accepted Answer

To solve the problem of counting unique paths in a grid while avoiding three consecutive moves in the same direction, we can use dynamic programming. The idea is to maintain a 3D DP array where `dp[x][y][d]` represents the number of ways to reach cell `(x, y)` with the last move being in direction `d` (0 for right, 1 for down, 2 for left, and 3 for up). We will iterate through the grid and update our DP table based on the allowed moves.

1. Initialize a 3D DP array with dimensions `(m+1) x (n+1) x 4` where `m` and `n` are the grid dimensions.
2. Set the starting position `dp[0][0][0]`, `dp[0][0][1]`, `dp[0][0][2]`, and `dp[0][0][3]` to 1, indicating one way to start without any moves.
3. Iterate through each cell in the grid, and for each direction, update the DP table based on the previous cell's values while ensuring not to exceed two consecutive moves in the same direction.

The time complexity of this approach is O(m * n) since we are iterating through each cell of the grid. The space complexity is O(m * n) due to the additional DP array used to store the counts for each direction.

```python
def count_paths(m, n):
    dp = [[[0] * 4 for _ in range(n + 1)] for _ in range(m + 1)]
    dp[0][0] = [1, 1, 1, 1]  # Starting point

for x in range(m):
        for y in range(n):
            for d in range(4):
                if d == 0 and y + 1 < n:  # Move right
                    dp[x][y + 1][0] += dp[x][y][0] + dp[x][y][1] + dp[x][y][2] + dp[x][y][3]
                if d == 1 and x + 1 < m:  # Move down
                    dp[x + 1][y][1] += dp[x][y][0] + dp[x][y][1] + dp[x][y][2] + dp[x][y][3]
                # Add similar conditions for left and up

return sum(dp[m - 1][n - 1])  # Sum paths to the bottom-right corner
```

It's important to consider edge cases such as very small grids (1x1, 1xN, Mx1) where the number of paths may be limited. Additionally, ensure to handle scenarios where the grid size is larger but has constraints that could limit movement.

Count Grid Paths Without Three Consecutive Moves

Anonymous

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Anonymous Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string