In our previous lessons, we've built a solid foundation in graph traversal, using DFS and BFS to explore explicit graphs, find connected components, and detect cycles. Now, we'll shift our perspective to a type of problem you'll encounter constantly in competitive programming: those involving 2D grids or mazes.
This lesson will teach you to see these grids not just as matrices, but as implicit graphs. The core learning outcome is to model a 2D grid as an implicit graph to solve traversal problems like shortest path or flood fill. Instead of being given an adjacency list, the connections (edges) are defined by rules, such as which cells are adjacent. Mastering this concept will allow you to apply all the graph algorithms you know directly to a vast new category of problems.
The Grid as an Implicit Graph
In many problems, you're given a 2D grid representing a map, a maze, or a game board. A cell might be empty, an obstacle, a start point, or an end point. When we view this as a graph:
- Each cell
(row, col)becomes a vertex. - An edge exists between two cells if you can move from one to the other. These edges are implicit—they are not stored in memory but are determined on the fly based on a set of rules.
The most common rule is movement in the four cardinal directions: North, South, East, and West. Sometimes, diagonal movement is also allowed, giving eight directions.
Explicitly building an adjacency list for a grid is possible, but usually inefficient. For an N x M grid, you would have N*M vertices, and the adjacency list could become very large. A much more elegant and standard approach in competitive programming is to use directional vectors.
The following video provides an excellent introduction to this idea. It explains why grids are implicit graphs and introduces the powerful directional vector technique that avoids building an explicit graph representation.
Breadth First Search grid shortest path | Graph Theory
This video by WilliamFiset clearly explains the concept of implicit graphs and the motivation for grid-based problems.
Watch from the introduction to understand why grids are a common and important form of implicit graph. The segment from explicit conversion shows how you could build an adjacency list, but highlights that it's often better to avoid this. Pay close attention to the section on directional vectors. This is the key implementation technique you will use for almost all grid problems.
As the video explained, we can define arrays to represent the change in row and column for each possible move. For 4-directional movement, the setup in C++ would be:
// Change in row for North, East, South, West
int dr[] = {-1, 0, 1, 0};
// Change in col for North, East, South, West
int dc[] = {0, 1, 0, -1};
// To get neighbors of cell (r, c):
for (int i = 0; i < 4; ++i) {
int new_r = r + dr[i];
int new_c = c + dc[i];
// Now, (new_r, new_c) is a potential neighbor
}
This simple loop effectively serves as our "adjacency list" for any given cell, allowing us to find its neighbors without any pre-computation.
Application 1: Flood Fill
One of the most direct applications of traversal on a grid is the Flood Fill algorithm. The goal is to find a connected area of cells that share a common property, starting from a given cell. This is conceptually identical to finding a connected component in an explicit graph.
For example, in a grid of '.' (land) and '#' (water), flood fill can find the entire area of a single island. This is often used to solve "count the islands" problems. You iterate through every cell of the grid. If you find an unvisited 'land' cell, you start a flood fill from there to visit the entire island, and you increment your island counter.
Flood fill can be implemented with either DFS or BFS. A recursive implementation is a natural fit for DFS, while an iterative implementation with a queue is essentially BFS.
The USACO Guide provides a clear, concise introduction to flood fill and its implementation.
Read the Introduction to get a formal definition and see how a grid is treated as an implicit graph. Next, study the C++ code in the Implementation section. This shows a classic recursive (DFS-based) flood fill, which is a fundamental pattern to know.
The "Water Puddles" problem described in the blog post below is a perfect example of this pattern, where you use DFS to find the size of connected components ('W' cells) while checking a specific boundary condition.
BFS and DFS Beginners Overview in c++
This resource shows a practical competitive programming problem solved with a grid traversal.
Review the C++ code and explanation in the section titled "Water Puddles - Solution". Notice how it iterates through the grid, and upon finding an unvisited 'W', it launches a DFS. The DFS itself tracks the size of the component and checks if it's a valid "puddle" by ensuring it doesn't touch the map's edge.
Application 2: Shortest Path in an Unweighted Grid
Remember our proof that BFS finds the shortest path in an unweighted graph? This property is immensely useful for grid problems. If each move between adjacent cells has a uniform cost (e.g., costs "1 step"), then finding the shortest path from a start cell 'S' to an end cell 'E' is a direct application of BFS.
The BFS naturally explores the grid in layers. Layer 0 is the start cell. Layer 1 is all cells reachable in 1 step. Layer 2 is all cells reachable in 2 steps, and so on. The first time we reach the end cell 'E', we are guaranteed to have found a shortest path.
The video from WilliamFiset that you watched earlier has a fantastic animated example of solving a dungeon escape problem with BFS. The following video from CodeNCode also provides a great C++-focused walkthrough.
L20 : BFS on 2D Grid | Graph Theory Part 1 | CodeNCode
This video from the CodeNCode channel demonstrates BFS on a 2D grid, focusing on the similarities with standard graph BFS and the C++ implementation.
Watch the initial examples to see how distances from a source cell are calculated for both 4-way and 8-way movement. The segment comparing graph BFS to grid BFS reinforces the idea that the logic is the same, just the representation of nodes (cells) and edges (adjacencies) changes. Finally, watch the code walkthrough. Pay attention to the isValid function, the use of direction arrays dx and dy, and how the queue stores pairs of coordinates.
Multi-Source BFS
A powerful variation is the Multi-Source BFS. Instead of starting from a single source cell, you can initialize the queue with multiple source cells. The BFS will then expand outwards from all sources simultaneously. This is extremely useful for problems like: "Find the empty cell that is farthest from any person ('G') on a map." You would simply start a BFS from all 'G' cells at once. The last empty cell visited by the BFS is the answer.
The "Safest Place" problem from the blog post is a classic example of this technique.
BFS and DFS Beginners Overview in c++
This section solves a problem using a Multi-Source BFS.
Read the section titled "Safest Place - Solution". Notice how the queue is initialized by pushing all of the "people" coordinates onto it before the main BFS loop begins. The distance matrix V then correctly stores the shortest distance from any person.
Conclusion
You have now connected your knowledge of fundamental graph traversals to the world of 2D grids. This is a significant step, as a huge number of problems in competitive programming can be modeled in this way.
Key Takeaways:
- A 2D grid can be treated as an implicit graph, where cells are vertices and adjacency is defined by movement rules.
- The most efficient way to handle neighbors is with directional vectors (e.g.,
dr,dcarrays), which avoids building an explicit adjacency list. - Flood Fill is used to find connected components on a grid and is a direct application of DFS (often recursively) or BFS (iteratively with a queue).
- BFS is the perfect algorithm for finding the shortest path in an unweighted grid, as it explores the grid in layers of increasing distance from the source.
- Multi-Source BFS is a powerful technique where the traversal starts from multiple cells simultaneously.
In the next lesson, we will explore another application of graph traversal: bipartite testing. We will learn how to use a 2-coloring approach during a traversal to determine if a graph's vertices can be divided into two disjoint sets, a property with many interesting applications.