Introduction

A common grid problem is to find the point whose nearest reference point is as far away as possible. In other words, for every candidate cell, you compute its distance to the closest point in a given set, then choose the candidate with the maximum of those minimum distances.

Define the Distance Model First

The right algorithm depends on what "distance" means.

On a grid, the most common choice is Manhattan distance:

distance((r1, c1), (r2, c2)) = |r1 - r2| + |c1 - c2|

That fits four-direction movement on an unweighted grid. If your problem uses diagonal movement or true geometric distance, the implementation changes.

Brute Force for Small Grids

For a small grid, the direct solution is easy to write: evaluate every cell against every reference point.

1def furthest_point(rows, cols, sources):
2    best_cell = None
3    best_distance = -1
4
5    for r in range(rows):
6        for c in range(cols):
7            nearest = min(abs(r - sr) + abs(c - sc) for sr, sc in sources)
8            if nearest > best_distance:
9                best_distance = nearest
10                best_cell = (r, c)
11
12    return best_cell, best_distance
13
14
15sources = [(0, 0), (4, 4)]
16print(furthest_point(5, 5, sources))

This is correct and often good enough if the grid is small. Its weakness is cost: every candidate cell compares itself against every source point.

Multi-Source BFS for Unweighted Grids

If movement is four-directional and every step has equal cost, a more scalable solution is multi-source breadth-first search. Start the BFS from all reference points at once. The last cell reached is one of the furthest points.

1from collections import deque
2
3
4def furthest_by_bfs(rows, cols, sources):
5    dist = [[-1] * cols for _ in range(rows)]
6    q = deque()
7
8    for r, c in sources:
9        dist[r][c] = 0
10        q.append((r, c))
11
12    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
13    last = None
14
15    while q:
16        r, c = q.popleft()
17        last = (r, c)
18        for dr, dc in directions:
19            nr, nc = r + dr, c + dc
20            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
21                dist[nr][nc] = dist[r][c] + 1
22                q.append((nr, nc))
23
24    return last, dist[last[0]][last[1]]
25
26
27sources = [(0, 0), (4, 4)]
28print(furthest_by_bfs(5, 5, sources))

This works because BFS explores cells in increasing distance order. Starting from all sources simultaneously means each cell is assigned the distance to its nearest source automatically.

Obstacles Change the Meaning

If some cells are blocked, BFS becomes even more useful because Manhattan distance no longer reflects actual travel cost. In that case, the furthest reachable point is the cell with the maximum BFS distance from the nearest source while respecting walls.

That is one reason it helps to think of the problem as shortest-path distance on a grid graph, not just a formula over coordinates.

Tie Handling

Several cells may be equally far from the source set. Decide the tie rule explicitly:

• first cell found
• smallest row then column
• all furthest cells

Many algorithms are correct mathematically but still fail tests because the tie-breaking rule was not defined.

Common Pitfalls

• Using Manhattan distance when the real problem includes blocked cells or weighted movement.
• Solving with brute force on a large grid when multi-source BFS would be much faster.
• Forgetting that the objective is maximum distance to the nearest source, not maximum distance to any source.
• Ignoring tie rules when several cells share the same best distance.
• Treating the problem as Euclidean geometry when it is really a graph-distance problem on a grid.

Summary

• The target cell maximizes its minimum distance to the given reference points.
• For small grids, brute force is easy and correct.
• For unweighted grid movement, multi-source BFS is the standard scalable solution.
• Obstacles make graph distance more important than simple coordinate formulas.
• Define the distance metric and tie-breaking rule before choosing an algorithm.