What is a Grid Graph?
A grid graph is a common graph structure typically used to simulate 2D or 3D maps, mazes, or chessboard problems. In algorithm problems, it's frequently used to assess mastery of algorithms like DFS, BFS, and shortest paths.
Common Directions:
- 4 directions: Up, Down, Left, Right
- 8 directions: Up, Down, Left, Right + Top-Left, Top-Right, Bottom-Left, Bottom-Right
- 6 directions (3D): Up, Down, Front, Back, Left, Right
Key Techniques:
- Maintain a
visitedset/array to avoid redundant visits. - Manage the search using queues (for BFS) or recursion (for DFS).
- Pay attention to boundary conditions (prevent out-of-bounds errors).
- Combine with advanced techniques like Union-Find or Priority Queues for complex solutions.
1. Classic DFS
Characteristics:
- Implemented via recursion or an explicit stack.
- Commonly used to search connected regions or count the size of connected components.
Applicable Scenarios:
- Traversing all connected grid cells.
- Solving problems like "How many connected regions are there?" or "What is the area of the largest region?".
Analogy: Island Explorer Just like finding an island on a map: you walk along the beach, and everywhere you can reach is considered one island. Then you move on to find the next island.
Corresponding Problems:
- LeetCode 200. Number of Islands
- LeetCode 547. Number of Provinces (Convert to graph DFS)
- LeetCode 695. Max Area of Island
- LeetCode 733. Flood Fill
2. Classic BFS
Characteristics:
- Implemented via a queue.
- Commonly used for searching the shortest path or expanding layer by layer.
Applicable Scenarios:
- Finding the shortest path from a starting point to an endpoint.
- Solving problems formulated as "expanding from a source point".
Analogy: Forest Firefighters
Like a fire breaking out in a forest, firefighters start from the source of the fire and spread outwards layer by layer to extinguish the flames until everything is put out.
Corresponding Problems:
- LeetCode 542. 01 Matrix
- LeetCode 994. Rotting Oranges
- LeetCode 752. Open the Lock
- LeetCode 1091. Shortest Path in Binary Matrix
3. Bidirectional BFS
Characteristics:
- Expands simultaneously from both the start and the end points.
- Terminates when the two searches meet.
- Drastically reduces search complexity.
Applicable Scenarios:
- Both starting point and endpoint are known.
- A faster search for the shortest path is required.
Analogy: Two-way Rescue Team
Two rescue teams set off from the camp and the missing location respectively. As soon as they meet midway, they quickly merge to complete the rescue mission.
Corresponding Problems:
4. Dijkstra's Algorithm
Characteristics:
- Applicable to weighted graphs (different cells or paths have different costs).
- Uses a Priority Queue to compute the weighted shortest path.
Applicable Scenarios:
- Needs to consider the varying costs of moving between different grid cells.
- Solving shortest path optimization problems.
Analogy: Food Delivery Driver
A delivery driver navigates through the city's streets and alleys. Each road takes a different amount of time, and they want to find the fastest delivery route.
Corresponding Problems:
- LeetCode 787. Cheapest Flights Within K Stops
- LeetCode 1514. Path with Maximum Probability
- LeetCode 1631. Path With Minimum Effort
5. Other Advanced Techniques
Characteristics:
- 3D grids, special structures (like honeycombs).
- Combining with advanced techniques like Union-Find, Topological Sorting, etc.
Applicable Scenarios:
- 3D mazes.
- Complex connectivity judgments.
- Scenarios requiring the integration of multiple algorithmic techniques.
Analogy: 3D Maze Explorer
You enter a 3D maze where you can not only move left and right but also climb up and down, with passages connecting every floor.
Corresponding Problems:
- LeetCode 130. Surrounded Regions (DFS/BFS)
- LeetCode 694. Number of Distinct Islands (DFS)
- LeetCode 1162. As Far from Land as Possible (Multi-source BFS)
- LeetCode 1254. Number of Closed Islands (DFS)