Problem $4.$ You are lost in a labyrinth consisting of a single straight line, di$-$

vided into n squares. There are no walls or other obstructions in this labyrinth,

but there is a set of inviolable rules.

$$ At any moment, you are painted with one of m colors.

$$ When you start, you are standing on the rst square of the labyrinth

painted blue.

$$ At any time, you can step into any square adjacent to your current square

$($except in the rst square you can only move forwards and in the nal

square you can only move backwards$).$

$$ When you step into a new square, you will be repainted with a new color.

Each square has a separate set of rules for how your color will change

when you step into it and for each square, these rules only depend on

what your color was when you stepped into the square.

$$ You can exit the labyrinth by stepping into the nal square while colored

blue.

Design an ecient algorithm to determine if you can escape the labyrinth and,

if so$,$ the fewest number of steps it will take to do so $($where stepping from one

square to an adjacent square counts as one step$).$

Formally, assume you are given an nm array A such that A$[$i$,$ j$]$ contains

the color you will be repainted to if you step into square i with color j$.$ You

can assume the colors are represented using the numbers $1$ through m and

that blue is represented by the number $1.$

Implement your algorithm with pseudocode, explain why it works, and nd

the running time.