search
HomeBackend DevelopmentPHP TutorialMinimum Cost to Make at Least One Valid Path in a Grid

1368. Minimum Cost to Make at Least One Valid Path in a Grid

Difficulty: Hard

Topics: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path

Given an m x n 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 grid[i][j] can be:

  • 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j 1])
  • 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
  • 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i 1][j])
  • 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some signs on the cells of the grid that point outside the grid.

You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Minimum Cost to Make at Least One Valid Path in a Grid

  • Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
  • Output: 3
  • Explanation: You will start at point (0, 0). The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
  • change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0)
  • change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3)
  • change the arrow to down with cost = 1 --> (3, 3) The total cost = 3.

Example 2:

Minimum Cost to Make at Least One Valid Path in a Grid

  • Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
  • Output: 0
  • Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

Minimum Cost to Make at Least One Valid Path in a Grid

  • Input: grid = [[1,2],[4,3]]
  • Output: 1

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1
  • 1

Hint:

  1. Build a graph where grid[i][j] is connected to all the four side-adjacent cells with weighted edge. the weight is 0 if the sign is pointing to the adjacent cell or 1 otherwise.
  2. Do BFS from (0, 0) visit all edges with weight = 0 first. the answer is the distance to (m -1, n - 1).

Solution:

We can use the 0-1 BFS approach. The idea is to traverse the grid using a deque (double-ended queue) where the cost of modifying the direction determines whether a cell is added to the front or back of the deque. The grid is treated as a graph where each cell has weighted edges based on whether its current direction matches the movement to its neighbors.

Let's implement this solution in PHP: 1368. Minimum Cost to Make at Least One Valid Path in a Grid

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function minCost($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Test Cases
$Minimum Cost to Make at Least One Valid Path in a Grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($Minimum Cost to Make at Least One Valid Path in a Grid) . "\n"; // Output: 3

$Minimum Cost to Make at Least One Valid Path in a Grid = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($Minimum Cost to Make at Least One Valid Path in a Grid) . "\n"; // Output: 0

$Minimum Cost to Make at Least One Valid Path in a Grid = [[1,2],[4,3]];
echo minCost($Minimum Cost to Make at Least One Valid Path in a Grid) . "\n"; // Output: 1
?>

Explanation:

  1. Direction Mapping: Each direction (1 for right, 2 for left, 3 for down, 4 for up) is mapped to an array of movement deltas [dx, dy].

  2. 0-1 BFS:

    • A deque is used to prioritize cells with lower costs. Cells that do not require modifying the direction are added to the front (unshift), while those that require a modification are added to the back (enqueue).
    • This ensures that cells are processed in increasing order of cost.
  3. Distance Array: A 2D array $dist keeps track of the minimum cost to reach each cell. It is initialized with PHP_INT_MAX for all cells except the starting cell (0, 0).

  4. Edge Weights:

    • If the current cell's sign matches the intended direction, the cost remains the same.
    • Otherwise, modifying the direction incurs a cost of 1.
  5. Termination: The loop terminates once all cells have been processed. The result is the value in $dist[$m - 1][$n - 1], representing the minimum cost to reach the bottom-right corner.

Complexity:

  • Time Complexity: O(m × n), since each cell is processed once.
  • Space Complexity: O(m × n), for the distance array and deque.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

  • LinkedIn
  • GitHub

The above is the detailed content of Minimum Cost to Make at Least One Valid Path in a Grid. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Working with Flash Session Data in LaravelWorking with Flash Session Data in LaravelMar 12, 2025 pm 05:08 PM

Laravel simplifies handling temporary session data using its intuitive flash methods. This is perfect for displaying brief messages, alerts, or notifications within your application. Data persists only for the subsequent request by default: $request-

Build a React App With a Laravel Back End: Part 2, ReactBuild a React App With a Laravel Back End: Part 2, ReactMar 04, 2025 am 09:33 AM

This is the second and final part of the series on building a React application with a Laravel back-end. In the first part of the series, we created a RESTful API using Laravel for a basic product-listing application. In this tutorial, we will be dev

Simplified HTTP Response Mocking in Laravel TestsSimplified HTTP Response Mocking in Laravel TestsMar 12, 2025 pm 05:09 PM

Laravel provides concise HTTP response simulation syntax, simplifying HTTP interaction testing. This approach significantly reduces code redundancy while making your test simulation more intuitive. The basic implementation provides a variety of response type shortcuts: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

cURL in PHP: How to Use the PHP cURL Extension in REST APIscURL in PHP: How to Use the PHP cURL Extension in REST APIsMar 14, 2025 am 11:42 AM

The PHP Client URL (cURL) extension is a powerful tool for developers, enabling seamless interaction with remote servers and REST APIs. By leveraging libcurl, a well-respected multi-protocol file transfer library, PHP cURL facilitates efficient execution of various network protocols, including HTTP, HTTPS, and FTP. This extension offers granular control over HTTP requests, supports multiple concurrent operations, and provides built-in security features.

12 Best PHP Chat Scripts on CodeCanyon12 Best PHP Chat Scripts on CodeCanyonMar 13, 2025 pm 12:08 PM

Do you want to provide real-time, instant solutions to your customers' most pressing problems? Live chat lets you have real-time conversations with customers and resolve their problems instantly. It allows you to provide faster service to your custom

Notifications in LaravelNotifications in LaravelMar 04, 2025 am 09:22 AM

In this article, we're going to explore the notification system in the Laravel web framework. The notification system in Laravel allows you to send notifications to users over different channels. Today, we'll discuss how you can send notifications ov

Explain the concept of late static binding in PHP.Explain the concept of late static binding in PHP.Mar 21, 2025 pm 01:33 PM

Article discusses late static binding (LSB) in PHP, introduced in PHP 5.3, allowing runtime resolution of static method calls for more flexible inheritance.Main issue: LSB vs. traditional polymorphism; LSB's practical applications and potential perfo

PHP Logging: Best Practices for PHP Log AnalysisPHP Logging: Best Practices for PHP Log AnalysisMar 10, 2025 pm 02:32 PM

PHP logging is essential for monitoring and debugging web applications, as well as capturing critical events, errors, and runtime behavior. It provides valuable insights into system performance, helps identify issues, and supports faster troubleshoot

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.