10.18 Solving Shortest Paths on Grids

Many shortest-path problems are not given as explicit graph structures. Instead, they appear as grids.

A grid may represent a maze, a game map, a warehouse floor, a robot workspace, an image, or a terrain model. Cells are vertices. Valid moves between neighboring cells are edges. Once you make that translation, ordinary graph algorithms apply directly.

This recipe shows how to model grid shortest-path problems cleanly and solve them with BFS or Dijkstra depending on movement costs.

Problem

Given a rectangular grid, find the shortest path from a start cell to a target cell.

For example:

S . . #
# # . #
. . . G

Where:

S is the start
G is the goal
. is an open cell
# is a blocked cell

The task is to move from S to G using valid grid moves.

Solution: BFS for Unweighted Grids

If every move has the same cost, use BFS.

Each open cell is a vertex.

Each valid move to a neighboring open cell is an edge with cost one.

package main

import "fmt"

type Point struct {
	Row int
	Col int
}

func shortestPathGrid(grid []string, start Point, goal Point) int {
	rows := len(grid)
	cols := len(grid[0])

	dist := make([][]int, rows)
	for r := 0; r < rows; r++ {
		dist[r] = make([]int, cols)
		for c := 0; c < cols; c++ {
			dist[r][c] = -1
		}
	}

	directions := []Point{
		{-1, 0},
		{1, 0},
		{0, -1},
		{0, 1},
	}

	queue := []Point{start}
	dist[start.Row][start.Col] = 0
	head := 0

	for head < len(queue) {
		current := queue[head]
		head++

		if current == goal {
			return dist[current.Row][current.Col]
		}

		for _, d := range directions {
			next := Point{
				Row: current.Row + d.Row,
				Col: current.Col + d.Col,
			}

			if next.Row < 0 || next.Row >= rows {
				continue
			}

			if next.Col < 0 || next.Col >= cols {
				continue
			}

			if grid[next.Row][next.Col] == '#' {
				continue
			}

			if dist[next.Row][next.Col] != -1 {
				continue
			}

			dist[next.Row][next.Col] =
				dist[current.Row][current.Col] + 1

			queue = append(queue, next)
		}
	}

	return -1
}

func main() {
	grid := []string{
		"S..#",
		"##.#",
		"...G",
	}

	fmt.Println(
		shortestPathGrid(
			grid,
			Point{0, 0},
			Point{2, 3},
		),
	)
}

Output:

The shortest route takes five moves.

Modeling the Grid as a Graph

You do not need to build an explicit adjacency list.

For a cell:

(row, col)

the neighbors are computed on demand:

(row - 1, col)
(row + 1, col)
(row, col - 1)
(row, col + 1)

This implicit graph representation saves memory.

For a grid with:

R rows and C columns

the graph has at most:

R × C vertices

and roughly:

4 × R × C edges

for four-direction movement.

The algorithm behaves exactly like BFS on an explicit graph.

Eight-Direction Movement

Some grids allow diagonal movement.

Use eight directions instead of four.

directions := []Point{
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1},
	{-1, -1},
	{-1, 1},
	{1, -1},
	{1, 1},
}

The shortest-path algorithm remains unchanged.

Only the neighbor-generation rule changes.

Be explicit about whether diagonal movement may pass through blocked corners. In grid pathfinding, that small rule often changes results.

Reconstructing the Path

To recover the actual route, store a parent cell for every visited cell.

parent := make([][]Point, rows)

for r := 0; r < rows; r++ {
	parent[r] = make([]Point, cols)
	for c := 0; c < cols; c++ {
		parent[r][c] = Point{-1, -1}
	}
}

When visiting a new cell:

parent[next.Row][next.Col] = current

After reaching the goal, follow parent pointers backward.

func buildGridPath(parent [][]Point, start Point, goal Point) []Point {
	path := []Point{}

	for current := goal; current != (Point{-1, -1}); {
		path = append(path, current)

		if current == start {
			break
		}

		current = parent[current.Row][current.Col]
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	if len(path) == 0 || path[0] != start {
		return nil
	}

	return path
}

This produces the sequence of cells on the shortest route.

Weighted Grids

Not all grids are unweighted.

A terrain map may assign costs:

plain = 1
forest = 3
mountain = 8

A robot map may assign costs based on risk, slope, energy use, or congestion.

When movement costs differ, BFS is no longer correct.

Use Dijkstra.

The structure remains familiar:

type GridState struct {
	Point Point
	Cost  int
}

The priority queue orders states by total cost.

Neighbor generation remains grid-based.

The only change is the relaxation formula:

candidate := dist[current.Row][current.Col] +
	cost(next.Row, next.Col)

Dijkstra is appropriate as long as all movement costs are nonnegative.

Obstacles and Bounds

Grid shortest-path code is dominated by validation.

A candidate move must usually pass four checks:

if row < 0 || row >= rows {
	continue
}

if col < 0 || col >= cols {
	continue
}

if grid[row][col] == '#' {
	continue
}

if alreadyVisited {
	continue
}

This is where most bugs occur.

Keep validation small and explicit.

A helper function often improves readability:

func inside(p Point, rows int, cols int) bool {
	return p.Row >= 0 &&
		p.Row < rows &&
		p.Col >= 0 &&
		p.Col < cols
}

Multiple Starts and Targets

Grid problems often involve many sources.

Examples:

Distance to nearest exit
Distance to nearest hospital
Distance to nearest enemy
Distance from all water cells to land
Fire spread time
Rotting oranges

Use multi-source BFS.

Initialize the queue with every starting cell.

for _, source := range sources {
	dist[source.Row][source.Col] = 0
	queue = append(queue, source)
}

The rest of BFS is unchanged.

This pattern is one of the most useful grid algorithms.

Walls That Can Be Broken

Some grid problems allow limited state changes.

Example:

You may break at most one wall.

A cell alone no longer describes the state.

You must include whether the wall break has been used.

type State struct {
	Row    int
	Col    int
	Broken int
}

The visited structure becomes three-dimensional:

visited[row][col][broken]

This transforms the problem into shortest path over an expanded state graph.

The grid is still the base structure, but the graph vertices are now states rather than cells.

Discussion

Grid problems are graph problems with implicit adjacency.

The most important skill is choosing the right state representation.

For simple mazes:

state = cell

For weighted terrain:

state = cell with accumulated cost

For keys and doors:

state = cell plus key mask

For limited wall breaks:

state = cell plus remaining breaks

Once the state is correct, the shortest-path algorithm is usually straightforward.

Bad state modeling is the main cause of wrong solutions.

Complexity

For a grid with:

R rows and C columns

BFS has:

Operation	Complexity
Vertices	O(RC)
Edges	O(RC)
Runtime	O(RC)
Memory	O(RC)

For weighted grids with Dijkstra:

Operation	Complexity
Runtime	O(RC log(RC))
Memory	O(RC)

If the state includes extra dimensions, multiply these bounds by the number of state variants.

For example, one wall break gives:

O(2RC)

which simplifies to:

O(RC)

but a key mask with K keys gives:

O(2^K RC)

Common Mistakes

Do not build an explicit graph unless you need to. Neighbor generation is simpler and usually more memory-efficient.

Do not use BFS when movement costs differ.

Do not mark only the cell as visited when the state includes additional information such as keys, fuel, or wall breaks.

Do not forget boundary checks.

Do not assume diagonal movement is allowed unless the problem states it.

Do not treat S and G as blocked cells.

Practical Applications

Grid shortest paths appear in:

Maze solving
Game pathfinding
Robotics
Warehouse automation
Image processing
Terrain navigation
Fire spread simulation
Cellular automata
Puzzle solvers
Emergency evacuation planning

Many of these systems begin as grid problems and later evolve into full graph models.

Takeaway

Grid shortest-path problems are ordinary graph problems with implicit neighbors. Use BFS when all moves have equal cost, Dijkstra when movement costs are nonnegative and variable, and multi-source BFS when many starting cells are active at once. The essential design decision is the state representation: sometimes a state is only a cell, and sometimes it must include extra information such as keys, wall breaks, fuel, or direction.