CSTATE1 - Chessboard State 1: National Chess Tournament

no tags 

Note: This is an easier version of the problems CSTATE2 and CSTATE3. A solution to those problems (except the I/O format) will pass here.

 

V Slovakistane sa rozhodli osadníci usporiadať národný šachový turnaj. 
Za prvé miesto sa dá získať diplom, a tak všetci hrajú ako o život. 
Keďže sa však nehrá na čas, vyskytol sa problém -- hráči nechceli priznať prehru.
Stále len tvrdili, že určite nemajú mat, však určite sa z tej situácie dá nejak dostať, keby len mali ešte chvíľku na rozmýšlanie... A možno ešte jednu...
Na budúci rok sa bude TMŠ v Slovakistane organizovať zas, ale je potrebné tento problém dovtedy nejako vyriešiť.
## Úloha
Pre daný popis šachovnice rozlíšte, či má niektorý z hráčov šach alebo mat.
Pritom berte do úvahy len obyčajné pohyby figúrok (komplikované ťahy ako
*rošáda*, *en passant*, *pohyb pešiakom o dva políčka vpred* a
*povýšenie pešiaka* sa v Slovakistane neakceptujú).
## Formát vstupu
V prvom riadku je číslo $1 \leq t \leq 1000$, udávajúce počet šachovníc na vstupe.
Nasleduje $t$ popisov šachovníc.
Každý popis šachovnice pozostáva z ôsmich riadkov, každý obsahujúci
osem znakov (teda šachovnica má klasické rozmery $8 \times 8$).
Tieto znaky sú `.KQRBHP`, reprezentujúce v tomto poradí voľné
políčko, kráľa, kráľovnú, vežu, strelca, koňa, a pešiaka. 
Bielemu hráčovi patrí horná strana šachovnice (skôr na vstupe) a jeho
figúrky sú označené malými písmenami. Teda bieli pešiaci sa pohybujú
smerom dole.
Čiernemu hráčovi patrí dolná strana šachovnice a jeho figúrky sú
označené veľkými písmenami. Jeho pešiaci sa pohybujú smerom hore.
Za každým popisom šachovnice je jeden prázdny riadok.
Počet ani poloha figúrok nijak nemusia byť dosiahnuteľné v
klasickej hre šachu, avšak môžete predpokladať, že na každej
šachovnici sa nachádza práve jeden biely kráľ (`k`) a práve jeden
čierny kráľ (`K`). 
Navyše, figúrky sa vo vstupoch budú vyskytovať nasledovne:
| Číslo sady | Nové figúrky |
| :--------: |------------------|
|  $1$ | Kráľ, kôň |
|  $2$ | Veža |
|  $3$ | Strelec, kráľovná|
|  $4$ | Pešiak |
## Formát výstupu
Pre každú šachovnicu vypíšte jeden riadok s jednou z nasledovných hlášok:
+   "Neutralna situacia.", ak žiaden z kráľov nie je ohrozený nepriateľskou figúrkou.
+   "Nemozna situacia.", ak sú obaja králi ohrození nepriateľskou figúrkou.
+   "{farba} hrac ma sach.", kde {farba} je "Biely", resp. "Cierny", ak
je kráľ tohto hráča v ohrození, ale existuje platný ťah niektorou
z jeho figúrok taký, po ktorom už v ohrození nebude.
+   "{farba} hrac ma mat.", kde {farba} je "Biely", resp. "Cierny", ak je
kráľ tohto hráča v ohrození, a neexistuje platný ťah niektorou z jeho
figúrok taký, po ktorom už v ohrození nebude.

The inhabitants of Slovakistan decided to organize a national chess tournament.

Since the first place prize is 1 point on SPOJ, everyone played as if their life was at stake.

However, since time was not measured in this chess tournament (unlike at most chess tournaments in the rest of the world), a problem occured - players took way too long to admit defeat.

They always just kept thinking and thinking, trying to find some move which would prevent their king from being taken. Just one more moment... And perhaps one more...

The inhabitants of Slovakistan are planning to hold the tournament next year as well. It would be great if a skilled programmer lent them a hand and got rid of this nuisance!

For a given description of a chessboard, decide its state - which player's king is under threat, and whether it is a Check or a Checkmate.

For the purposes of this problem only take into account basic moves of every chesspiece; complicated moves such as Castling, En passant, moving a pawn 2 squares or Promotion are not accepted in Slovakistan.

Input

The first line of the input contains the integer 1 ≤ t ≤ 2000 - the number of chessboards. t descriptions of a chessboard follow.

Each description of a chessboard consists of 8 rows, each consisting of 8 characters (the chessboard is of the traditional dimensions 8x8).

These characters are from the set {.KQRBHPkqrbhp}, representing in this order an empty square, king, queen, rook, bishop, knight (horse), and pawn.

The pieces belonging to the White player are marked by lowercase characters; the upper side of the chessboard (first in the input) belongs to him, hence white pawns move downwards.

The pieces belonging to the Black player are makred by uppercase characters; the lower side of the chessboard belongs to him, hence black pawns move upwards.

A blank line follows after every chessboard.

The number or placement of the pieces may by all means be impossible to reach in a standard game of chess, however you may assume that on every chessboard there is exactly

one white king ('k') and one black king ('K'). 

Output

For each chessboard output one line with one of the following messages:

  • "Safe", if neither players' kings are being threatened
  • "Impossible", if both players' kings are being threatened
  • "{colour} Check", where {colour} is either "Black" or "White", if the respective player's king is being threatened, and there exists at least one valid move by any of his pieces after which his king is no longer threatened
  • "{colour} Checkmate", where {colour} is either "Black" or "White",  if the respective player's king is being threatened, and there exists no valid move by any of his pieces after which his king is no longer threatened

Additional note

There are 13 input files "0" through "12".

In order to make finding mistakes easier and/or let you implement various chesspieces one by one, with the exception of the example (file #0), the following holds:

Chesspiece      Appears first in file #
King 1
Knight 1
Rook 3
Bishop 5
Queen 5
Pawn 8


Additionally, after submission you can view extra information about the result of each file by clicking the result text ("accepted","wrong answer",...).

As an example, if you have received WA, the extra information looks like so:

File #5: Result is WA, message is 'Test Case 47: Your answer: Black Checkmate; Correct answer: Black Check', time = 0.100000, mem = 123456

Note that the message can go haywire if your program does something unexpected, such as end before reading all input. 

Example

Input:
7
....k...
........
...H....
........
...h....
........
....K...
........

........
....h...
..k.....
.....H..
...K....
........
........
........

k..H....
...H....
.HH.....
........
........
......K.
........
........

k..H....
...H....
.HH.....
........
........
......K.
.r......
........

K.....Rr
R.h....r
........
........
rr......
.....k..
........
........

k.......
.......R
........
...B....
.R......
......K.
..q.....
........

........
..PPP...
..PkP...
...Pp...
...K....
........
........
........
Output:
Impossible
Safe
White Checkmate
White Check
Black Checkmate
White Check
Black Check

This is my first time using my own judge/master judge; although this problem is 'interactive' in order to get the info message, the input is all given first before your output is read, so hopefuly it should have no effect. If you have a suspicion it is doing something funky, do let me know :)


hide comments
Michael Kharitonov: 2017-07-10 14:18:59

Can I move a pawn to the last rank without promotion?

RE: as stated, no moves except basic movement is taken into account, i.e. promotion does not exist (although unless I am missing something, promotion makes no difference in this problem)

FORW: but can I move the pawn to the last rank without promotion to prevent checkmate? Is only promotion itself forbidden or all moves that require promotion are forbidden too?

RE: yes, you simply act as if promotion doesn't exist - there is nothing special about moving a pawn to the last rank

Last edit: 2017-07-11 21:59:35

Added by:Hodobox
Date:2017-07-03
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem