A helicopter starting at the top left corner is descending (in a 2D space, for the purpose of this question) towards the ground. It has an autopilot mode and a manual mode.
The autopilot mode behaves as follows:
- If the space directly below is free, descend to it.
- Otherwise move a step left or right, totally at random. (It may move multiple steps in this manner.)
And it keeps repeating these two steps until it hits the ground. The manual mode is more smart and will find the optimal path to the ground, even if this requires moving upwards, or some skillful manoeuvring.
Your job is to determine if
- The autopilot will pass in the given scenario,
- The autopilot might fail in the given scenario,
- The autopilot will fail, but the manual mode will pass, or
- Both modes will fail (there is no valid path to the ground).
Input
- Given scenario as a 1d or 2d non-empty array, using two different characters to represent free and blocked spaces. Punctuation optional.
- Optional: dimensions of array
Output
One of four predefined characters indicating which of the cases has occurred.
Sample data
Using 0 (empty) and 1 (blocked) in input, 1 2 3 4 in output (as numbered above)
0 0 0 0
0 1 0 0
0 0 0 1
1 1 0 0
Output: 1
0 0 1 0
1 0 0 1
0 0 0 0
0 1 1 0
0 0 0 1
Output: 2
(The helicopter will encounter the 1 in the fourth row, and it is possible it will trap itself at the end of row 5, if on autopilot mode)
0 0 0 1 0
0 1 1 0 0
0 1 0 0 0
0 0 0 1 0
1 1 1 1 0
Output: 3
(This requires moving upwards, so the autopilot fails)
1 0 0
0 0 0
Output: 4
0 0 0 0 1
1 1 1 0 0
1 0 0 1 0
0 1 0 0 0
0 0 1 1 1
Output: 4