Data Structures and Algorithms Fall 2022

Question 2

Let G be a n × n grid, where n ∈ Z+. G stores a single non–negative integer value on each cell. There may be duplicated values on different cells in G. We need to search for a sequence of cells in G starting at (i, j) until it reaches a cell with value v. The values of the cells in the sequence increase by one until it reaches the cell with value v. The search process visits the neighborhood of a cell in the following order: Up, Right, Bottom, Left.

For example, consider the grid below. The red path describes the sequence starting at (2, 0) and ending

at a location with the value of 6.

0 1 2 3 4

0 0 2 4 6 2

1 1 2 8 2 3

2 2 4 7 8 2

3 3 4 5 8 9

4 3 4 6 0 2

Explain a solution to the problem using a DFS traversal on G starting at a cell (i, j) until it finds the sequence of cells until that ends at a cell with value v.

Remember to visit the neighborhood of a cell in the indicated order. Consider the case when no such sequence is possible.