Grid Graphs
You've traversed graphs. Now treat grids as graphs. Solve Number of Islands, rotting oranges, and multi-source BFS problems on 2D matrices.
Lessons
1. Introduction to Grid Graphs
Cells as nodes, adjacency as edges
2. What Grid Problems Solve
Islands, regions, distances
3. When to Use Grid Techniques
Flood fill vs multi-source vs BFS
4. Multi-Source BFS Pattern
The multi-source pattern
5. Problem - Get All Keys
LC 864 - locks, keys, and bitmasks
6. Get All Keys - Why Naive Fails
Same cell, different keys = different states
7. Get All Keys - Defining the State
(row, col, keys) with bitmask
8. Get All Keys - Transition
Lock needs key, key updates mask
9. Get All Keys - Base Cases
Find @, count total keys first
10. Get All Keys - Implementation
Queue with 3D state tracking
11. Get All Keys - Time and Space
O(mn · 2^K) for K keys
12. Problem - Pacific Atlantic
LC 417 - flows to both oceans
13. Pacific Atlantic - Why Naive Fails
Reverse: which cells reach ocean?
14. Pacific Atlantic - Defining the Approach
Two visited sets, one per ocean
15. Pacific Atlantic - Core Logic
Multi-source from each border
16. Pacific Atlantic - Implementation
Intersection of both reachable sets
17. Problem - Surrounded Regions
LC 130 - flip surrounded Os
18. Surrounded Regions - Why Naive Fails
Find unsurrounded, flip the rest
19. Surrounded Regions - Defining the Approach
Mark boundary-connected first
20. Surrounded Regions - Core Logic
Border DFS, then scan interior
21. Surrounded Regions - Implementation
Temporary marker T, then replace
22. Boundary DFS Pattern
The boundary pattern
23. Problem - Shortest Bridge
LC 934 - connect two islands
24. Shortest Bridge - Solution
DFS first island, BFS to second
25. Shortest Bridge - Why This Works
Multi-source BFS finds shortest bridge
26. Quiz: Grid Pattern Recognition
Which grid pattern?
27. Quiz: Boundary Techniques
Boundary vs interior techniques
28. Common Mistakes in Grid Graphs
Infinite loops, slow multi-BFS
29. Problem - Minimum Moves with Rotations
LC 1210 - grid rotations
30. Minimum Moves with Rotations - Solution
The solution
31. Problem - Escape the Spreading Fire
LC 2258 - fire escape
32. Escape the Spreading Fire - Solution
The solution
33. Section Recap
Flood fill to multi-source