Find a path across the grid that avoids bad neighborhoods

Assignment Help Basic Computer Science

Reference no: EM131361557

Consider a city whose streets are defined by an X ×Y 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 X × Y matrix BAD, where BAD[i,j] = "yes" if and only if the intersection between streets i and j is in a neighborhood to avoid.

(a) Give an example of the contents of BAD such that there is no path across the grid avoiding bad neighborhoods.

(b) Give an O(XY ) algorithm to find a path across the grid that avoids bad neighborhoods.

(c) Give an O(XY ) algorithm to find the shortest path across the grid that avoids bad neighborhoods. You may assume that all blocks are of equal length. For partial credit, give an O(X²Y²) algorithm.

Reference no: EM131361557

Questions Cloud

Complete the production budget on the budgets tab : Complete the Production Budget on the Budgets tab below by using the information found in the budgeted balance sheet above.

Amounts of the three parts of the investment : The interest from the first investment was 4 times the interest from the second. Find the amounts of the three parts of the investment.

Find the marginal revenue for the production levels : Assume that a demand equation is given by q = 9000 minus 100p. Find the marginal revenue for the given production levels(values of q). (Hint: Solve the demand equation for p and use R(q)= qp.)

Describe his or her professional license information : Identify the licensed mental health counselor you have selected to interview.Describe his or her professional license, setting, population/specialization, and any other relevant information.Explain why you selected this person to interview.

Find a path across the grid that avoids bad neighborhoods : Give an O(XY ) algorithm to find the shortest path across the grid that avoids bad neighborhoods. You may assume that all blocks are of equal length. For partial credit, give an O(X2Y2) algorithm.

Policy claim on a topic of your choice : ENG 101 -Remember, A CLAIM OF POLICY is a claim that argues for a specific course of action to solve a problem. So, your essay should discuss a problem, and PROPOSE a viable solution that is backed up with credible research.

Mean in the context of question : A) Interpret the value of b in the sample regression line. What does it mean in the context of this question? B) Compute the linear correlation between "daily sales" and "temperature." Note: Express your answer to 4 decimal places of accuracy.

Strategic analysis walmart : Describe the industry you a re investigating. Identify the company you are researching along with the mission, vision, values, and strategic plan. Be sure to answer the following questions: Strategic Analysis Walmart

Examine the key factors affecting the demand : From the scenario for Katrina's Candies, examine the key factors affecting the demand for and the supply of a good in general and Katrina's Candies specifically.

User Account

All Pages