PK

PKBytes

Explore tracks
Chapter 10: Matrices, Grids and Multidimensional Arrays
10.04Beginner / Intermediate6 topics14 min6 interactive animations

Neighborhood reasoning

Neighbourhood reasoning is how most grid algorithms move: 4- and 8-direction neighbours, direction vectors, inside-grid checks, obstacles and multi-source starts.

Learning goals

  • Generate neighbours with direction vectors
  • Write one reusable bounds and obstacle check
  • Start a search from many cells at once

Prerequisites

Traversal patterns
10.04.1

4-direction

In 4-direction movement a cell (r, c) has up to four neighbours: up, right, down and left, at offsets (-1, 0), (0, 1), (1, 0) and (0, -1). This is the usual meaning of adjacent in grid path problems, and the neighbours are at Manhattan distance 1.

Pick a cell and read which of its four neighbours are valid.

Java
1static final int[] DR = {-1, 0, 1, 0}, DC = {0, 1, 0, -1};     // up, right, down, left
2for (int d = 0; d < 4; d++) {
3    int nr = r + DR[d], nc = c + DC[d];
4    // process (nr, nc) after the bounds check
5}

Neighbours, direction vectors and bounds checks

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
1
1
1
1me
0
1
2
1
1
1
1
Chosen cellValid neighbourWall (blocked)

valid neighbours

none yet
Setup

Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.

Step 1 / 6
Java
1static final int[] DR4 = {-1, 0, 1, 0}, DC4 = {0, 1, 0, -1};                 // up, right, down, left
2static final int[] DR8 = {-1, -1, 0, 1, 1, 1, 0, -1}, DC8 = {0, 1, 1, 1, 0, -1, -1, -1};   // adds the diagonals
3static List<int[]> neighbors(int[][] g, int r, int c, boolean eight) {
4    int[] dr = eight ? DR8 : DR4, dc = eight ? DC8 : DC4;
5    List<int[]> out = new ArrayList<>();
6    for (int d = 0; d < dr.length; d++) {
7        int nr = r + dr[d], nc = c + dc[d];
8        if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;   // outside the grid
9        if (g[nr][nc] == 0) continue;                                              // wall
10        out.add(new int[]{nr, nc});
11    }
12    return out;
13}

Live state

r

1

c

1

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L4r=1 c=1Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.
2L10d=0 (dr, dc)=(-1, 0) (nr, nc)=(0, 1)up: (0, 1) is open: a valid neighbour.
3L9d=1 (dr, dc)=(0, 1) (nr, nc)=(1, 2)right: (1, 2) is a wall.
4L10d=2 (dr, dc)=(1, 0) (nr, nc)=(2, 1)down: (2, 1) is open: a valid neighbour.
5L10d=3 (dr, dc)=(0, -1) (nr, nc)=(1, 0)left: (1, 0) is open: a valid neighbour.
6L12return=33 valid neighbours out of 4 directions. Corners and edges have fewer neighbours, which is why the bounds check is needed.
10.04.2

8-direction

8-direction movement adds the four diagonals, so a cell has up to eight neighbours, at Chebyshev distance 1 (like a chess king). Use it for “touching including corners” rules such as Minesweeper counts or the game of life.

Switch the direction option to 8 and compare the neighbour count at a corner.

Java
1static final int[] DR8 = {-1, -1, 0, 1, 1, 1, 0, -1}, DC8 = {0, 1, 1, 1, 0, -1, -1, -1};   // clockwise from up
2int count = 0;
3for (int d = 0; d < 8; d++) {
4    int nr = r + DR8[d], nc = c + DC8[d];
5    if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) count++;
6}

Neighbours, direction vectors and bounds checks

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
1
1
1
1me
0
1
2
1
1
1
1
Chosen cellValid neighbourWall (blocked)

valid neighbours

none yet
Setup

Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.

Step 1 / 6
Java
1static final int[] DR4 = {-1, 0, 1, 0}, DC4 = {0, 1, 0, -1};                 // up, right, down, left
2static final int[] DR8 = {-1, -1, 0, 1, 1, 1, 0, -1}, DC8 = {0, 1, 1, 1, 0, -1, -1, -1};   // adds the diagonals
3static List<int[]> neighbors(int[][] g, int r, int c, boolean eight) {
4    int[] dr = eight ? DR8 : DR4, dc = eight ? DC8 : DC4;
5    List<int[]> out = new ArrayList<>();
6    for (int d = 0; d < dr.length; d++) {
7        int nr = r + dr[d], nc = c + dc[d];
8        if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;   // outside the grid
9        if (g[nr][nc] == 0) continue;                                              // wall
10        out.add(new int[]{nr, nc});
11    }
12    return out;
13}

Live state

r

1

c

1

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L4r=1 c=1Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.
2L10d=0 (dr, dc)=(-1, 0) (nr, nc)=(0, 1)up: (0, 1) is open: a valid neighbour.
3L9d=1 (dr, dc)=(0, 1) (nr, nc)=(1, 2)right: (1, 2) is a wall.
4L10d=2 (dr, dc)=(1, 0) (nr, nc)=(2, 1)down: (2, 1) is open: a valid neighbour.
5L10d=3 (dr, dc)=(0, -1) (nr, nc)=(1, 0)left: (1, 0) is open: a valid neighbour.
6L12return=33 valid neighbours out of 4 directions. Corners and edges have fewer neighbours, which is why the bounds check is needed.
10.04.3

Direction vectors

A direction vector (dr, dc) is the change in row and column for one step. Storing the vectors in two small arrays (or one int[][]) replaces four or eight copies of nearly identical code with one loop. A knight's moves, hex grids and longer jumps are just other sets of vectors.

Keep the order consistent (for example clockwise) so direction indexes can be reused, such as (d + 1) % 4 for a right turn.

Directiondrdc
Up-10
Right01
Down10
Left0-1

Neighbours, direction vectors and bounds checks

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
1
1
1
1me
0
1
2
1
1
1
1
Chosen cellValid neighbourWall (blocked)

valid neighbours

none yet
Setup

Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.

Step 1 / 6
Java
1static final int[] DR4 = {-1, 0, 1, 0}, DC4 = {0, 1, 0, -1};                 // up, right, down, left
2static final int[] DR8 = {-1, -1, 0, 1, 1, 1, 0, -1}, DC8 = {0, 1, 1, 1, 0, -1, -1, -1};   // adds the diagonals
3static List<int[]> neighbors(int[][] g, int r, int c, boolean eight) {
4    int[] dr = eight ? DR8 : DR4, dc = eight ? DC8 : DC4;
5    List<int[]> out = new ArrayList<>();
6    for (int d = 0; d < dr.length; d++) {
7        int nr = r + dr[d], nc = c + dc[d];
8        if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;   // outside the grid
9        if (g[nr][nc] == 0) continue;                                              // wall
10        out.add(new int[]{nr, nc});
11    }
12    return out;
13}

Live state

r

1

c

1

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L4r=1 c=1Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.
2L10d=0 (dr, dc)=(-1, 0) (nr, nc)=(0, 1)up: (0, 1) is open: a valid neighbour.
3L9d=1 (dr, dc)=(0, 1) (nr, nc)=(1, 2)right: (1, 2) is a wall.
4L10d=2 (dr, dc)=(1, 0) (nr, nc)=(2, 1)down: (2, 1) is open: a valid neighbour.
5L10d=3 (dr, dc)=(0, -1) (nr, nc)=(1, 0)left: (1, 0) is open: a valid neighbour.
6L12return=33 valid neighbours out of 4 directions. Corners and edges have fewer neighbours, which is why the bounds check is needed.
10.04.4

Inside-grid checks

Before touching g[nr][nc] confirm that 0 <= nr < R and 0 <= nc < C. Do it first, with short-circuit &&, so an invalid index is never evaluated. Wrapping the check in a helper inBounds(r, c) keeps search code readable; a border of sentinel cells (padding the grid with walls) is an alternative that removes the check entirely.

Pick a corner cell: some directions land outside and are skipped.

Java
1static boolean inBounds(int r, int c, int R, int C) { return r >= 0 && r < R && c >= 0 && c < C; }
2if (inBounds(nr, nc, R, C) && g[nr][nc] != WALL) {
3    // safe to use (nr, nc)
4}

Neighbours, direction vectors and bounds checks

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
1
1
1
1me
0
1
2
1
1
1
1
Chosen cellValid neighbourWall (blocked)

valid neighbours

none yet
Setup

Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.

Step 1 / 6
Java
1static final int[] DR4 = {-1, 0, 1, 0}, DC4 = {0, 1, 0, -1};                 // up, right, down, left
2static final int[] DR8 = {-1, -1, 0, 1, 1, 1, 0, -1}, DC8 = {0, 1, 1, 1, 0, -1, -1, -1};   // adds the diagonals
3static List<int[]> neighbors(int[][] g, int r, int c, boolean eight) {
4    int[] dr = eight ? DR8 : DR4, dc = eight ? DC8 : DC4;
5    List<int[]> out = new ArrayList<>();
6    for (int d = 0; d < dr.length; d++) {
7        int nr = r + dr[d], nc = c + dc[d];
8        if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;   // outside the grid
9        if (g[nr][nc] == 0) continue;                                              // wall
10        out.add(new int[]{nr, nc});
11    }
12    return out;
13}

Live state

r

1

c

1

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L4r=1 c=1Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.
2L10d=0 (dr, dc)=(-1, 0) (nr, nc)=(0, 1)up: (0, 1) is open: a valid neighbour.
3L9d=1 (dr, dc)=(0, 1) (nr, nc)=(1, 2)right: (1, 2) is a wall.
4L10d=2 (dr, dc)=(1, 0) (nr, nc)=(2, 1)down: (2, 1) is open: a valid neighbour.
5L10d=3 (dr, dc)=(0, -1) (nr, nc)=(1, 0)left: (1, 0) is open: a valid neighbour.
6L12return=33 valid neighbours out of 4 directions. Corners and edges have fewer neighbours, which is why the bounds check is needed.
10.04.5

Multi-source starts

A multi-source search starts from several cells at once: put all of them in the queue with distance 0 before the search begins. The wave then spreads from every source simultaneously, so each cell receives the distance to its nearest source. This solves “distance to the nearest 0” and “how long until everything rots”.

Switch the BFS animation to multi-source mode.

Java
1Deque<int[]> queue = new ArrayDeque<>();
2int[][] dist = new int[R][C];
3for (int[] row : dist) Arrays.fill(row, -1);
4for (int r = 0; r < R; r++)
5    for (int c = 0; c < C; c++)
6        if (g[r][c] == 2) { dist[r][c] = 0; queue.offer(new int[]{r, c}); }   // every source starts at distance 0

BFS on a grid: shortest path and multi-source distances

Interactive · edit the input

Your input

Try

grid · 3 × 5

01234
0
0
·
▇
·
·
1
▇
·
·
·
·
2
▇
·
·
·
·
Cell being expandedReached (distance shown)WallSource

queue (front first)

(0,0)
Setup

Start at the top-left cell with distance 0.

Step 1 / 14
Java
1static int shortestPath(int[][] g) {                     // 4-directional moves, 0 = wall
2    int R = g.length, C = g[0].length;
3    int[][] dist = new int[R][C]; for (int[] row : dist) Arrays.fill(row, -1);
4    Deque<int[]> queue = new ArrayDeque<>();
5    // single source: (0, 0); multi-source: every cell equal to 2, all at distance 0
6    dist[0][0] = 0; queue.offer(new int[]{0, 0});
7    while (!queue.isEmpty()) {
8        int[] cur = queue.poll();
9        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
10            int r = cur[0] + d[0], c = cur[1] + d[1];
11            if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0 || dist[r][c] != -1) continue;
12            dist[r][c] = dist[cur[0]][cur[1]] + 1;           // first arrival is the shortest, because BFS goes level by level
13            queue.offer(new int[]{r, c});
14        }
15    }
16    return dist[R - 1][C - 1];                               // -1 when unreachable; multi-source: max over all cells
17}

Live state

sources

1

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L5sources=1Start at the top-left cell with distance 0.
2L12cell=(0,0) dist=0Expand (0,0) at distance 0: reached (0,1)=1.
3L12cell=(0,1) dist=1Expand (0,1) at distance 1: reached (1,1)=2.
4L12cell=(1,1) dist=2Expand (1,1) at distance 2: reached (1,2)=3, (2,1)=3.
5L12cell=(1,2) dist=3Expand (1,2) at distance 3: reached (1,3)=4, (2,2)=4.
6L12cell=(2,1) dist=3Expand (2,1): every open neighbour is already reached or blocked.
7L12cell=(1,3) dist=4Expand (1,3) at distance 4: reached (0,3)=5, (1,4)=5, (2,3)=5.
8L12cell=(2,2) dist=4Expand (2,2): every open neighbour is already reached or blocked.
9L12cell=(0,3) dist=5Expand (0,3) at distance 5: reached (0,4)=6.
10L12cell=(1,4) dist=5Expand (1,4) at distance 5: reached (2,4)=6.
11L12cell=(2,3) dist=5Expand (2,3): every open neighbour is already reached or blocked.
12L12cell=(0,4) dist=6Expand (0,4): every open neighbour is already reached or blocked.
13L12cell=(2,4) dist=6Expand (2,4): every open neighbour is already reached or blocked.
14L16return=6The bottom-right cell is 6 steps away, the minimum, because BFS reaches cells in order of distance.
10.04.6

Obstacles

Obstacles (walls, water, blocked cells) are cells you may not enter. Treat them exactly like out-of-bounds: reject the neighbour in the same check. Decide a clear convention for the grid (for example 0 = wall, 1 = open) and apply it in the single neighbour helper.

The grid in the animation marks walls as blocked neighbours.

Java
1static List<int[]> openNeighbors(int[][] g, int r, int c) {
2    List<int[]> out = new ArrayList<>();
3    for (int d = 0; d < 4; d++) {
4        int nr = r + DR[d], nc = c + DC[d];
5        if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;   // outside
6        if (g[nr][nc] == 0) continue;                                              // wall
7        out.add(new int[]{nr, nc});
8    }
9    return out;
10}

Neighbours, direction vectors and bounds checks

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
1
0
1
1
1
1me
0
1
2
1
1
1
1
Chosen cellValid neighbourWall (blocked)

valid neighbours

none yet
Setup

Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.

Step 1 / 6
Java
1static final int[] DR4 = {-1, 0, 1, 0}, DC4 = {0, 1, 0, -1};                 // up, right, down, left
2static final int[] DR8 = {-1, -1, 0, 1, 1, 1, 0, -1}, DC8 = {0, 1, 1, 1, 0, -1, -1, -1};   // adds the diagonals
3static List<int[]> neighbors(int[][] g, int r, int c, boolean eight) {
4    int[] dr = eight ? DR8 : DR4, dc = eight ? DC8 : DC4;
5    List<int[]> out = new ArrayList<>();
6    for (int d = 0; d < dr.length; d++) {
7        int nr = r + dr[d], nc = c + dc[d];
8        if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;   // outside the grid
9        if (g[nr][nc] == 0) continue;                                              // wall
10        out.add(new int[]{nr, nc});
11    }
12    return out;
13}

Live state

r

1

c

1

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L4r=1 c=1Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.
2L10d=0 (dr, dc)=(-1, 0) (nr, nc)=(0, 1)up: (0, 1) is open: a valid neighbour.
3L9d=1 (dr, dc)=(0, 1) (nr, nc)=(1, 2)right: (1, 2) is a wall.
4L10d=2 (dr, dc)=(1, 0) (nr, nc)=(2, 1)down: (2, 1) is open: a valid neighbour.
5L10d=3 (dr, dc)=(0, -1) (nr, nc)=(1, 0)left: (1, 0) is open: a valid neighbour.
6L12return=33 valid neighbours out of 4 directions. Corners and edges have fewer neighbours, which is why the bounds check is needed.

Practice ladder

Now try it yourself

Easy

  • List the 4-direction neighbours of (1, 1) in a 3 × 3 grid
  • How many neighbours does a corner cell have with 8 directions?

Medium

  • Count the mines around each cell of a Minesweeper board
  • Why is the bounds check written before the g[nr][nc] test?

Advanced

  • Use a padded grid with a wall border to remove all bounds checks from a BFS

Key takeaways

  • Direction arrays turn neighbour code into one loop.
  • Check bounds first, then obstacles; wrap both in one helper.
  • Seed all sources at distance 0 for a multi-source search.