Sam is navigating a giant maze of pumpkins, and they need your help to find the exit before it is too late!
The maze can be represented as an $$$n \times m$$$ grid, each cell consisting of one of the following objects:
- A ".", denoting an empty space.
- A "P", denoting an impassable pumpkin.
- A "C", denoting a candy corn, which Sam may collect by passing through.
- A "J", denoting a jack-o'-lantern, which Sam may only pass through by spending a candy corn (if they currently have no candy corns, it acts as an impassable space).
- An "S", denoting Sam's starting space.
- An "E", denoting the exit to the pumpkin patch.
Additionally, Sam can only move in four directions: up, down, left, and right; each taking one unit of time. Given the description of the maze Sam finds themselves in, output the shortest amount it would take for Sam to reach the exit space, our output "SPOOKED!" if it is impossible for Sam to escape.
The input will begin with a single line containing two space-separated integers, $$$n$$$ and $$$m\ (1 \leq n, m \leq 100)$$$. The next $$$n$$$ lines will each contain exactly $$$m$$$ characters, describing the maze. The $$$j^{\text{th}}$$$ character on the $$$i^{\text{th}}$$$ line, denoted as $$$c_{i,j}$$$, satisfies the following requirements:
- $$$c_{i,j} \in \{$$$"."$$$, $$$"P"$$$, $$$"C"$$$, $$$"J"$$$, $$$"S"$$$, $$$"E"$$$\}$$$.
- There exists exactly one $$$(i, j) \in \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$$$ such that $$$c_{i,j} = $$$ "S" and exactly one such that $$$c_{i,j} =$$$ "E".
Finally, let $$$d$$$ denote the number of candy corns in the maze, that is, the number of values $$$(i, j)$$$ such that $$$c_{i,j} = C$$$. It is guaranteed that $$$0 \leq d \leq 8$$$.
The output should consist of exactly one line containing either the phrase "SPOOKED!" if it is impossible for Sam to escape, or the minimum amount of time it would take Sam to reach the exit space.
5 5S..PC.PPP..P....P..J...JE
16
1 10SCCCCJJJJE
9
3 3EJJJSJJJJ
SPOOKED!
