Problem Statement | |||||||||||||
| State machines occur frequently in computer science literature. At any given point in time, a state machine is in a particular state p. After receiving an input symbol, the machine updates its state. The potential input symbols in this problem are 0, 1, 2, or 3. The String[] transitions describes how the state machine M behaves. Each element of transitions will contain 4 space delimited integers. The integers in element i (0-based) describe how M reacts to input while in state i. For example, if element 3 is "0 4 2 3", then M will transition from state 3 to state 0, 4, 2, or 3 depending on whether 0, 1, 2, or 3 are received as input, respectively. Our state machine M is unfortunately out of control. We do not know which state M is currently in. To rectify the situation, we want to find a string s and a state h such that, after feeding s into M one symbol at a time, M will definitely be in state h. Considering all possible pairs of s and h, return the length of the shortest s. If no such pairs exist, return -1. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
| - | transitions will contain between 1 and 20 elements inclusive. | ||||||||||||
| - | Each element of transitions will have the form "w x y z" where w, x, y, and z are integers, without extra leading zeros, between 0 and k-1 inclusive. Here k is the number of elements in transitions. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||