You are given two integers m and n, representing the dimensions of an m $ imes$ n grid, and a $2$D integer array waitCost of size m $ imes$ n.

You start at cell (0, 0) at second $1$ by paying an initial entry cost of $(0 + 1) imes (0 + 1) = 1$. Your objective is to reach the bottom right cell (m - 1, n - 1).

At each second $t \geq 1$:

• If $t$ is odd:

  • You may move to an adjacent cell, either right to (r, c + 1) or down to (r + 1, c). The direction of each move must alternate from the previous move, though the very first move can be in either direction. Entering cell (r, c) incurs a cost of $(r + 1) imes (c + 1)$.

  • Alternatively, you may choose to wait at your current cell (r, c) and pay a cost of waitCost[r][c].

• If $t$ is even:

  • You cannot move and must wait at your current cell (r, c), paying a cost of waitCost[r][c].

Return the minimum total cost required to reach cell (m - 1, n - 1).

Constraints:

• $1 \leq$ m, n $\leq 10^5$

• $2 \leq$ m $ imes$ n $\leq 10^5$

• waitCost.length $=$ m

• waitCost[0].length $=$ n

• $0 \leq$ waitCost[i][j] $\leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.