Consider a city whose streets are defined by an n times m grid. We are intereste

Question

Consider a city whose streets are defined by an n times m grid. We are interested in walking from the upper left-hand corner of the grid to the lower right-hand corner. Unfortunately, the city has bad neighborhoods, whose intersections we do not want to walk in. We are given an n times m matrix BAD, where BAD[i, j] = true if and only if the intersection between streets i and j is in a neighborhood to avoid. Give at least two examples of possible grids (BAD) such that there is no path across the grid avoiding bad neighborhoods. Give an O(n times m) algorithm to check if there is a path across the grid that avoids bad neighborhoods. Give an O(n middot m) algorithm to find a shortest path across the grid that avoids bad neighborhoods.

Explanation / Answer

Solution

(a) B means BAD, G means good

1. GBB

2. BBG   

(b)

We can implement a basic breath first backtracking algorithm which visits each block no more than one time. Backtracking, visited array, each i, j is visited one time. That is, we start at the higher left corner and put each adjacent block in a queue. If we visited the lower right corner we found a path otherwise if we have visited every adjacent block and not have visited the lower right corner then there’s no path.

(c)

We can use a modified version of (b) for this task. We start with an extra cost matrix which is initialized with 0 for each not bad block and ‘X’ otherwise. If we start at an arbitrary block [k, l] and put its adjacent blocks on our queue, we set their cost entry to C[k,l] + 1. At the end, we get a cost matrix which allows us to find the shortest paths.

But let’s look at an example first.

1 G G B G B G 0 1 X 7 X 9

2 B G B G G G X 2 X 6 7 8

3 B G G G B G X 3 4 5 X 9

4 G B G B B G 0 X 5 X X 10

On the right is the initial matrix and on the right is the cost matrix. We can easily find the shortest path by starting at [i, j] and traverse backwards by choosing the next block which got one cost less than the current one.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.