Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Individual Programming Problem

Unit:MIT202 Complexity and Algorithms

Due Date:XX/XX/20XX

Total Marks:This assessment is worth 40% of the full marks in the unit.

Instructions:

1. Students are required to cover all stated requirements.

2. Your submission must be uploaded to Moodle in zip file including all source codes and documentation/manual/report.

3. Include a title/cover page containing the subject title and code and the name, student id numbers.

4. Please save the document as MIT202_Firstname_Surname_StudentNumber[assessment2].zip

Requirements:

● The assignment is an individual programming project, which is to write a program that solves the defined algorithm problem.

● You need to carefully follow the input format and generate sensible output. If the program crashed during testing, you may lose the corresponding marks in specific tests.

● This assignment should be submitted on XX/XX/XXXX 4pm through Turnitin.Any submission after the due date will be dealt with late submission penalties.

You’ve just stolen a brand-new car, but the owner has locked the car with The Spade, a mechanical lock on the steering wheel, which prevents you from making left turns. In addition, to avoid car accidents and otherwise attracting attention, you aren’t going to make any U-turns either. You want to reach your chop -shop1 as quickly as possible, and since you can drive down straight streets very quickly, your primary goal is to minimize the number of (right) turns you make. But if two paths have the same number of right turns, then you want to minimize the straight-line distance.

Fortunately, you have a map of the city, so you can plan out a route that uses no left turns and no U-turns. Even better, the map comes in electronic form as an m × n grid of cells, each marked as either empty (navigable) or blocked(unnavigable). At each cell you visit, you can continue in the direction you were going, or turn right. Two examples of no-left-turn maps are shown below.

Give an efficient algorithm to find a no-left-turn and no-U-turn path through an m × n map using the minimum number of right turns, or report that no such path exists. Among all paths with the minimum number of right turns, your algorithm should return the path minimizing the straight-line distance (i.e., the number of straight steps). (Hint: For intuition, solve the left- hand map in Figure 1.) 

The input of the program is a m x n number matrix in a text file, where 1 means blocked and 0 means empty. Your program should display the best path (or no path if does not exist) 

Submission

Bundle all your source code and documentation into a zip file named MIT202_Firstname_Surname_StudentNumberr[assessment2].zip

Submit it to the Moodle system by the due date. 

Marking Criteria

[15 marks] Quality of individual’s solution

[10 marks] The discussion and improvement during the testing process [25 marks] The quality of the final program