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 n times m matrix BAD, where BAD_[i j]= true if and only if intersection between streets I and j is in a neighbourhood to avoid. Give at least two examples of possible grids (BAD) such that there is no path across the grid avoiding bad neighbourhoods. Give an O(n middot m) algorithm to check if there is a path across the grid that avoids bad neighbourhoods. Give an O(n middot m) algorithm to find a shortest path across the grid that avoids bad neighbourhoods