Problem K
Knight Search
Alice is a chess knight living in Chessland (an $N \times N$ board). The cells in Chessland are numbered from $1$ to $N^2$ in row major order. Each cell has an UPPERCASE alphabet character assigned to it. The Chessland is described by a string $S$ of length $N^2$ (in row major order). For example for $N = 5$ and $S$ = “IXIXXXXCXAXSXXPXXCSXAGXXX”, the Chessland that Alice lives in looks like this:
12345 ----- 1|IXIXX 2|XXCXA 3|XSXXP 4|XXCSX 5|AGXXX
As Alice is a chess knight, she can only move from cell $(a, b)$ to cell $(c, d)$ in Chessland if and only if $(a-c)^2 + (b-d)^2 = 5$. Alice wonder if she can find her favorite string “ICPCASIASG” in Chessland by starting from a cell with character ‘I’ and finds the other $9$ characters by jumping around in Chessland using chess knight movements. Alice can visit the same cell more than once.
You are of course Bob the computing bee and your job is to help her decide the answer.
Input
The first line of input consists of 1 integer: $N$ ($1 \leq N \leq 100$). The second line contains a string $S$ of $N^2$ UPPERCASE characters [‘A’..‘Z’] that describe Chessland.
Output
Print “YES” if Alice can find string “ICPCASIASG” in Chessland or print “NO” otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 IXIXXXXCXAXSXXPXXCSXAGXXX |
YES |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 THEQUICKBROWNFOXJUMPSOVER |
NO |
