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