Game Field Matrix Puzzle - Grid Coding Interview

Problem A game field is an N x M grid. Each cell is either empty (0) or contains a power-up (1). A player starts at (0, 0) and must reach (N-1, M-1) moving only right or down. The player collects all power-ups on their path. Part 1: Find the path that collects the maximum number of power-ups. Part 2: After collecting power-ups along the optimal path, those cells become 0. Find the maximum power-ups collectible on a second independent path from (0,0) to (N-1,M-1) on the modified grid. Example: Fo…