Interesting optimisation problem : Travelling in three ways in a nxm grid

Правка en2, от haitax511, 2025-06-06 15:34:25

Bob is playing a game on a 2D grid with $$$n$$$ rows and $$$m$$$ columns. He starts at the top-left corner, cell $$$(1, 1)$$$, and his goal is to reach the bottom-right corner, cell $$$(n, m)$$$.

Bob can move in the following ways:

  • Choose an index $$$i$$$ ($$$1 \le i \le k$$$) and:
  • Move down by $$$A[i]$$$ rows: from $$$(x, y)$$$ to $$$(x + A[i], y)$$$
  • Move right by $$$B[i]$$$ columns: from $$$(x, y)$$$ to $$$(x, y + B[i])$$$
  • Move diagonally down-right by $$$C[i]$$$ cells: from $$$(x, y)$$$ to $$$(x + C[i], y + C[i])$$$

Each such move has a cost of $$$1$$$.

You are also guaranteed that each of the arrays $$$A$$$,$$$B$$$ and $$$C$$$ contain $$$1$$$.

You are given the integers $$$n$$$, $$$m$$$, $$$k$$$ and the arrays $$$A$$$, $$$B$$$, and $$$C$$$, each of length $$$k$$$. Your task is to compute the minimum cost to reach cell $$$(n, m)$$$ starting from $$$(1, 1)$$$.

Теги dp, grid, optimisation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский haitax511 2025-06-06 15:46:12 20 Tiny change: '1, 1)$. \n' -> '1, 1)$. \n\n$n,m,k\leq 1O^3$\n'
en2 Английский haitax511 2025-06-06 15:34:25 1
en1 Английский haitax511 2025-06-06 14:11:46 885 Initial revision (published)