403053: GYM100985 D MaratonIME plays Chess

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. MaratonIME plays Chesstime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard outputThis problem is boring as duck.Kawakami, Marcos

Our dear Nathan, when a little child, used to like chess a lot, but this was a long time ago. One of these days he was challenged by @luisgust to a chess match and, as he is a guy that likes hard challenges, he accepted it. The problem is that Nathan keeps forgetting the rules of the game, so he asked you to help him determine if a given opponent's piece can be captured in one move.

Chess, in MaratonIME, is represented as a matrix of characters. Instead of playing with black and white pieces, they play with uppercase and lowercase letters. Nathan has chosen to play with the lowercase letters.

Besides that, as usual, the positions on the matrix are given in the following coordinates system: Each position is a pair with a character between a and h (inclusive), representing the column, and an integer between 1 and 8 (inclusive), representing the row. For exemple, the position d2 refers to the fourth column (from left to right) and second row (from bottom to top), and the position f6 refers to the sixth column and sixth row. Lowercase letters start on the bottom of the grid, on lines 1 and 2.

Here position A is adjacent position B if A shares a vertex with B, that is, if the distance between their rows is at most one and the distance between their columns is at most one. For example, the position c4 is adjacent to 8 positions: b3, b4, b5, c3, c5, d3, d4 and d5.

They decided to play a simplified version of chess. To help you, they gave you the following manual on how to play it:

  • The pawn, represented by p or P, can capture pieces that share a diagonal and is in front of it, that is, the lowercase pawn on c4 can capture pieces at b5 or d5.
  • The knight, represented by c or C, makes L-shaped moves in any of the 8 possible directions, that is, it moves two positions in any direction and after that one position in a direction that is perpenticular to the first one. A knight on c4 can capture, in one move, pieces on positions a3, a5, b2, b6, d2, d6, e3 and e5.
  • The rook, represented by t or T, can capture pieces that are on the same row or the same column as it, as long as no other piece lies between them. For example, a rook on c4 can capture any piece on column c or row 4, as long as there is no other piece in between. If the rook is on c4 and there is another piece on c6, the rook can't capture pieces on c7 and c8.
  • The bishop, represented by b or B, can capture any piece on one of its diagonals as long as there are no piece between them (diagonaly). For example, the bishop on c4 can capture a piece on f7 as long as there are no piece on d5 and e6.
  • The queen, represented by r or R, can capture any piece that lies on the same row, column or diagonal, given there are no pieces in between, as if it were a bishop and a rook at the same time.
  • The king, represented by k or K, can capture any piece that is adjacent to it.
  • The character . represents an empty position.

Given a matrix representing a chess board and an opponent's piece, your program needs to determine whether you can capture it with one of your pieces. It is guaranteed that each player has at most two bishops, two rooks, two knights, eight pawns, one king and one queen.

Input

The input begins with 8 lines with 8 characters each, representing the chess board. The first line contains the characters on the positions a8, b8, ... , h8. The second line contains the characters on positions a7, b7, ... , h7, and so on. After that follows a line containing the position of the opponent's piece you wish to capture.

Output

Print a single line containing the word Sim if it is possible to capture the piece or Nao otherwise.

ExamplesInput
TCBRKBCT
PPPPPPPP
........
........
........
........
pppppppp
tcbrkbct
d8
Output
Nao
Input
........
........
........
..R.....
...p....
........
........
........
c5
Output
Sim

加入题单

上一题 下一题 算法标签: