SJSU Weekly Practice Problems 1/2

#### Start

2022-01-02 20:00 AKST

## SJSU Weekly Practice Problems 1/2

#### End

2022-01-09 20:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -139 days 21:05:13

168:00:00

0:00:00

# Problem EFlow Free

Flow Free is a puzzle that is played on a 2D grid of cells, with some cells marked as endpoints of certain colors and the rest of cells being blank.

To solve the puzzle, you have to connect each pair of colored endpoints with a path, following these rules:

• there is a path connecting two points with the same color, and that path also has that color

• all cells in the grid are used and each cell belongs to exactly one path (of the same color as the endpoints of the path)

The rules imply that different colored paths cannot intersect.

The path is defined as a connected series of segments where each segment connects two neighbouring cells. Two cells are neighbours if they share a side (so all segments are either horizontal or vertical). By these definitions and rules above, each colored cell will be an endpoint of exactly one segment and each blank cell will be an endpoint of exactly two segments.

In this problem we will consider only the $4 \times 4$ puzzle, with $3$ or $4$ pairs of colored endpoints given.

Your task is to determine if a given puzzle is solvable or not.

## Input

The input consists of $4$ lines, each line containing $4$ characters. Each character is from the set $\{ R, G, B, Y, W\}$ where $W$ denotes the blank cells and the other characters denote endpoints with the specified color. You are guaranteed that there will be exactly $3$ or $4$ pairs of colored cells. If there are $3$ colors in the grid, $Y$ will be omitted.

## Output

On a single line output either “solvable” or “not solvable” (without the quotes).

Sample Input 1 Sample Output 1
RGBW
WWWW
RGBY
YWWW

solvable

Sample Input 2 Sample Output 2
RGBW
WWWW
RGBW
YWWY

not solvable