Package g1301_1400.s1368_minimum_cost_to_make_at_least_one_valid_path_in_a_grid

Class Solution

java.lang.Object
g1301_1400.s1368_minimum_cost_to_make_at_least_one_valid_path_in_a_grid.Solution
public class Solution extends Object
1368 - Minimum Cost to Make at Least One Valid Path in a Grid.<p>Hard</p> <p>Given an <code>m x n</code> grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of <code>grid[i][j]</code> can be:</p> <ul> <li><code>1</code> which means go to the cell to the right. (i.e go from <code>grid[i][j]</code> to <code>grid[i][j + 1]</code>)</li> <li><code>2</code> which means go to the cell to the left. (i.e go from <code>grid[i][j]</code> to <code>grid[i][j - 1]</code>)</li> <li><code>3</code> which means go to the lower cell. (i.e go from <code>grid[i][j]</code> to <code>grid[i + 1][j]</code>)</li> <li><code>4</code> which means go to the upper cell. (i.e go from <code>grid[i][j]</code> to <code>grid[i - 1][j]</code>)</li> </ul> <p>Notice that there could be some signs on the cells of the grid that point outside the grid.</p> <p>You will initially start at the upper left cell <code>(0, 0)</code>. A valid path in the grid is a path that starts from the upper left cell <code>(0, 0)</code> and ends at the bottom-right cell <code>(m - 1, n - 1)</code> following the signs on the grid. The valid path does not have to be the shortest.</p> <p>You can modify the sign on a cell with <code>cost = 1</code>. You can modify the sign on a cell <strong>one time only</strong>.</p> <p>Return <em>the minimum cost to make the grid have at least one valid path</em>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/02/13/grid1.png" alt="" /></p> <p><strong>Input:</strong> grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> You will start at point (0, 0). The path to (3, 3) is as follows. (0, 0) &ndash;> (0, 1) &ndash;> (0, 2) &ndash;> (0, 3) change the arrow to down with cost = 1 &ndash;> (1, 3) &ndash;> (1, 2) &ndash;> (1, 1) &ndash;> (1, 0) change the arrow to down with cost = 1 &ndash;> (2, 0) &ndash;> (2, 1) &ndash;> (2, 2) &ndash;> (2, 3) change the arrow to down with cost = 1 &ndash;> (3, 3) The total cost = 3.</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/02/13/grid2.png" alt="" /></p> <p><strong>Input:</strong> grid = [[1,1,3],[3,2,2],[1,1,4]]</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> You can follow the path from (0, 0) to (2, 2).</p> <p><strong>Example 3:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2020/02/13/grid3.png" alt="" /></p> <p><strong>Input:</strong> grid = [[1,2],[4,3]]</p> <p><strong>Output:</strong> 1</p> <p><strong>Constraints:</strong></p> <ul> <li><code>m == grid.length</code></li> <li><code>n == grid[i].length</code></li> <li><code>1 <= m, n <= 100</code></li> <li><code>1 <= grid[i][j] <= 4</code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • minCost

      public int minCost(int[][] grid)