Problem 44379. One track five lanes
Find the minimum number of lane changes necessary to cross the entire track without running into any obstacles
A track is represented by a 5xN board (with 5 lanes and N squares in each lane). Some of the squares are blocked and the runner cannot pass through them (red blocks in the image above). The runner may only move forward or laterally (i.e. advancing or switching lanes), and cannot run into or jump over any obstacles. Diagonal or backward moves through the board are also not allowed. The runner may start and finish in any arbitrary lane of his choosing. Your job is to determine, given the track, the minimum number of lane changes necessary to finish the race.
The input matrix will be a 5xN matrix with 1's representing blocked squares and 0's representing available/free squares. The output of your function should be a number indicating the minimum number of lane changes necessary to finish the race. For example, the track shown in the picture above would be represented as:
x = [0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0];
and your function
n = fivelanes(x);
should return n=2, since there are multiple paths available (e.g. yellow line in the picture above) that would allow the runner to reach the end of the track with only 2 lane changes, but none that would allow the runner to complete the track with only one or less lane changes.
Good luck!
Small print: You may assume that there will always be a direct path between the start and finish requiring only forward- and lateral- movements. The testsuite does not include cases where there are no possible paths of this form. Lane changes are counted identically irrespective of whether they involve adjacent or non-adjacent lanes (i.e. switching from lane 1 to lane 4 counts as one lane-change, just the same as switching from lane 1 to lane 2). When switching lanes the runner may not run over obstacles (i.e. switching from lane 1 to lane 3 is not possible if there is an obstacle in lane 2 at that point in the track). Below a few examples of tracks and possible minimal-lane-changes paths (note: optimal paths are not unique; in all of these examples the optimal number of lane-changes is, coincidentally, 5)
Solution Stats
Problem Comments
-
4 Comments
why can't I use bwlabel from the imaging toolbox?
this one took a while to solve lol
No matter what you do you always fail the last test, it really ruins the problem.
Why is my solution (at size73) first when I sort low to high, though the leading solution is down at 43?
And really, more than 60 tests? It took me almost as long to copy and paste the the test cases as it did to solve the problem. I don't object to the number of tests, but can you please lump them, esp. as Submit just says "assertion failed" with no clue where the problem is?
Solution Comments
Show commentsProblem Recent Solvers70
Suggested Problems
-
25208 Solvers
-
Find state names that start with the letter N
1220 Solvers
-
Back to basics 12 - Input Arguments
594 Solvers
-
Make a vector of prime numbers
636 Solvers
-
190 Solvers
More from this Author38
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!