Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,372 views
in Online Assessments by Expert (44,360 points) | 1,372 views

4 Answers

0 like 0 dislike
Best answer
Given a grid of size mxn,
count the number of ways you can go from (0, 0) to end of grid.

 

You can move down or right only. You don't like taking boring paths, so you move in the same direction continuously at max 2 times. eg: grid [3, 4] : (0, 0) -> (0, 1) -> (0, 2) -> (0, 3) is not valid since you moved right 3 times. (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 3) -> (2, 3) is one of the valid paths.
by Expert (44,360 points)
0 like 0 dislike
class GridPath:
    def gridPath(self, row, col):
        self.DOWN = 0
        self.RIGHT = 1

        x, y = 0, 0
        self.res = 0
        self.move(x, y, row, col, -1, -1)

        return self.res

    def move(self, x, y, row, col, last, second_last):
        if x >= row or y >= col:
            return
        elif x == row-1 and y == col -1:
            self.res += 1
        else:
            if last == second_last == self.DOWN:
                self.move(x + 1, y, row, col, self.RIGHT, last)
            elif last == second_last == self.RIGHT:
                self.move(x, y + 1, row, col, self.DOWN, last)
            else:
                self.move(x + 1, y, row, col, self.RIGHT, last)
                self.move(x, y + 1, row, col, self.DOWN, last)
by Expert (44,360 points)
0 like 0 dislike

Let's use a 4D DP to solve this. Here, f(i, j, m, r) denotes the number of ways from (0, 0) -> (i, j), with the last move being m (0 = down, 1 = right) and r tracking the repeat state.

 

def solve(m, n):
 
  @functools.lru_cache(None)
  def dp(i, j, last_move, repeated):
    if i < 0 or j < 0: return 0
    if i == 0 and j == 0: return 1

    ans = 0
    if last_move == 0: # 
      if repeated: ans = dp(i-1, j, 0, False)
      else: ans = dp(i-1, j, 1, False) + dp(i-1, j, 1, True)
    elif last_move == 1:
      if repeated: ans = dp(i, j-1, 0, False)
      else: ans = dp(i, j-1, 0, False) + dp(i, j-1, 0, True)

    return ans

  return dp(m, n, 0, False) + dp(m, n, 0, True) + dp(m, n, 1, False) + dp(m, n, 1, True)
by Expert (44,360 points)
0 like 0 dislike

C++/ BFS

Assuming a path exits, we can do a simple dfs from top left to bottom right.

  1. The BFS call will also store two counters right, down which we will increment every time we move in that direction.
  2. If right < 2 && down < 2 we have can move in both the directions (right and down). When you move right, set down to 0 and vice-versa.
  3. If right < 2 more right and set down counter to 0.
  4. If down < 2 more down and set right counter to 0.
#define pp pair<int, int>
void bfs(vector< vector<int> > &grid, int x, int y, int right, int down, int &ct, queue<pp> q){
	if(x == grid.size()-1 && y == grid[0].size()-1){
		ct += 1;
        q.push({x,y});
        while(!q.empty()){
            if(q.size() == 1)
                cout << "(" <<q.front().first << " " <<  q.front().second << ") -> " << ct <<"\n";
            else
                cout << "(" <<q.front().first << " " <<  q.front().second << "), ";
            q.pop();
        }
        return;
	}
    
    q.push({x,y});
	if(right <2 && down <2){
		if(y+1 < grid[0].size() && grid[x][y+1] == 1) dfs(grid, x, y+1, right+1, 0, ct, q);
		if(x+1 < grid.size() && grid[x+1][y] == 1) dfs(grid, x+1, y, 0, down+1, ct, q);
	} else if(right < 2){
		if(y+1 < grid[0].size() && grid[x][y+1] == 1) dfs(grid, x, y+1, right+1, 0, ct, q);
	} else{
		if(x+1 < grid.size() && grid[x+1][y] == 1) dfs(grid, x+1, y, 0, down+1, ct, q);
	}
    
    return;
}

int main() {
    vector<vector<int>> grid{{1,1,1},{1,1,1},{1,1,1}};
    queue<pp> q;
    int ct = 0;
    
    bfs(grid, 0, 0, 0, 0, ct, q);

}

Output

(0 0), (0 1), (0 2), (1 2), (2 2) -> 1
(0 0), (0 1), (1 1), (1 2), (2 2) -> 2
(0 0), (0 1), (1 1), (2 1), (2 2) -> 3
(0 0), (1 0), (1 1), (1 2), (2 2) -> 4
(0 0), (1 0), (1 1), (2 1), (2 2) -> 5
(0 0), (1 0), (2 0), (2 1), (2 2) -> 6
by Expert (44,360 points)