407301: GYM102757 F Maze Design

Alice has traveled back in time to Ancient Greece to meet one of her greatest idols, the famous inventor Daedulus. When Alice visits, Daedulus is analyzing a few maze passageways that he is considering including in his latest creation, the soon-to-be famous Labyrinth. Alice jumps at the opportunity to help Daedulus and needs to build a solver that determines if a given maze passageway is solvable or not.

A maze passageway consists of $$$3$$$ rows that each have $$$n$$$ positions. Each position can either be blocked, which means that Alice cannot move through that position, or open, which means that Alice can move through that position. To solve a particular maze passageway, a person can move in any of the cardinal directions, as long as they don't move into a blocked position or go out of bounds of the passageway. Alice can start in any of the $$$3$$$ rows at the first position and can successfully solve the maze if she can reach the final position at any of the $$$3$$$ rows.

Given a particular maze passageway that meets these criteria, you must output Solvable! if Alice can solve the maze passageway and Unsolvable! otherwise.

The first line will consist of a single integer $$$n$$$ ($$$2 \leq n \leq 10^4$$$), which gives the number of positions per row. The next $$$3$$$ lines consist of a string, $$$s$$$, with $$$n$$$ characters that are either 0 or 1, representing a row of the maze passage way. If $$$s_i = $$$ 0, then the $$$i$$$th position in that row is open, and if $$$s_i = $$$ 1, then the $$$i$$$th position in that row is blocked.

Output Solvable! if the maze passageway is solvable and Unsolvable! otherwise.

2
00
10
00

Solvable!

2
01
10
10

Unsolvable!