Pattern Reference
Grid Patterns
"Neighbor iteration, matrix prefix sum, BFS/DFS on grid, island patterns, shortest distance, multi-source."
Loading...
Deep Dive Tutorial
Grid problems are graph problems in disguise: each cell is a node, adjacent cells are connected by edges. The same BFS/DFS algorithms apply, but with a direction array for neighbors and bounds checking. The key choice: BFS for shortest path, DFS for connected components, multi-source BFS for distance from any source.
Grid BFS/DFS template
const dirs = [[0,1],[0,-1],[1,0],[-1,0]]; // 4-directional
// const dirs = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]; // 8-directional
const inBounds = (r, c, m, n) => r >= 0 && r < m && c >= 0 && c < n;
// DFS flood fill — mark connected region
function dfs(grid, r, c, visited) {
if (!inBounds(r,c,grid.length,grid[0].length)) return;
if (visited[r][c] || grid[r][c] === 0) return;
visited[r][c] = true;
for (const [dr,dc] of dirs) dfs(grid, r+dr, c+dc, visited);
}
// BFS shortest path to any target
function bfs(grid, startR, startC) {
const m=grid.length, n=grid[0].length;
const dist = Array.from({length:m},()=>new Array(n).fill(-1));
dist[startR][startC] = 0;
let queue = [[startR, startC]];
while (queue.length) {
const next = [];
for (const [r,c] of queue) {
for (const [dr,dc] of dirs) {
const nr=r+dr, nc=c+dc;
if (!inBounds(nr,nc,m,n) || dist[nr][nc] !== -1 || grid[nr][nc] === 0) continue;
dist[nr][nc] = dist[r][c] + 1;
next.push([nr,nc]);
}
}
queue = next;
}
return dist;
}
// Multi-source BFS — distance from nearest source
function multiSourceBFS(grid, sources) {
const m=grid.length, n=grid[0].length;
const dist = Array.from({length:m},()=>new Array(n).fill(Infinity));
const queue = [];
for (const [r,c] of sources) { dist[r][c] = 0; queue.push([r,c]); }
let i = 0;
while (i < queue.length) {
const [r,c] = queue[i++];
for (const [dr,dc] of dirs) {
const nr=r+dr, nc=c+dc;
if (!inBounds(nr,nc,m,n)||dist[nr][nc]!==Infinity) continue;
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr,nc]);
}
}
return dist;
}Worked Problems
map
Grid problem pattern selector:
- "Count connected regions" → DFS flood fill, count DFS starts
- "Shortest path from A to B" → BFS, return level when B reached
- "Distance from nearest X for all cells" → Multi-source BFS from all X cells
- "Which cells are boundary-connected?" → DFS from all boundary cells, mark them
- "Weighted grid (different costs)" → Dijkstra or 0-1 BFS (if costs are 0 or 1)
- "Max island size / sum" → DFS, return size instead of void
Mark visited early: In BFS, mark cells as visited when ENQUEUED, not dequeued. Prevents the same cell from being added to queue multiple times.
- "Count connected regions" → DFS flood fill, count DFS starts
- "Shortest path from A to B" → BFS, return level when B reached
- "Distance from nearest X for all cells" → Multi-source BFS from all X cells
- "Which cells are boundary-connected?" → DFS from all boundary cells, mark them
- "Weighted grid (different costs)" → Dijkstra or 0-1 BFS (if costs are 0 or 1)
- "Max island size / sum" → DFS, return size instead of void
Mark visited early: In BFS, mark cells as visited when ENQUEUED, not dequeued. Prevents the same cell from being added to queue multiple times.