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)