Problem: Count Routes to Climb a Rectangular Grid

Try to solve the Count Routes to Climb a Rectangular Grid problem.

Statement

You are given an $n \times m$ grid of characters grid and an integer d. The grid consists of empty cells '.' and obstacle cells '#'.

A climbing route is a sequence of distinct cells $(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)$ satisfying the following conditions:

The route starts at any empty cell in the bottom row, where $r_1 = n - 1$ and grid $[r_1][c_1] =$ '.'.
The route ends at any empty cell in the top row, where $r_k = 0$ and grid $[r_k][c_k] =$ '.'.
Every visited cell along the route is empty, meaning grid $[r_t][c_t] =$ '.' for all $1 \leq t \leq k$ .
The row index is nonincreasing at every step, meaning $r_{t+1} \leq r_t$ for all $1 \leq t < k$ .
The Euclidean distance between any two consecutive cells along the route is at most d, meaning $\sqrt{(r_{t+1} - r_t)^2 + (c_{t+1} - c_t)^2} \leq d$ for all $1 \leq t < k$ .

Return the total number of valid climbing routes.

Constraints:

Try to solve the Count Routes to Climb a Rectangular Grid problem.

You are given an $n \times m$ grid of characters grid and an integer d. The grid consists of empty cells '.' and obstacle cells '#'.

A climbing route is a sequence of distinct cells $(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)$ satisfying the following conditions:

The route starts at any empty cell in the bottom row, where $r_1 = n - 1$ and grid $[r_1][c_1] =$ '.'.
The route ends at any empty cell in the top row, where $r_k = 0$ and grid $[r_k][c_k] =$ '.'.
Every visited cell along the route is empty, meaning grid $[r_t][c_t] =$ '.' for all $1 \leq t \leq k$ .
The row index is nonincreasing at every step, meaning $r_{t+1} \leq r_t$ for all $1 \leq t < k$ .
The Euclidean distance between any two consecutive cells along the route is at most d, meaning $\sqrt{(r_{t+1} - r_t)^2 + (c_{t+1} - c_t)^2} \leq d$ for all $1 \leq t < k$ .

Return the total number of valid climbing routes.

Constraints: