Problem B: Can U Win ?
Time Limit: 1 sec
You are playing Chess with your little sister. Unfortunately She is too smart for you.
You are about to lose with only a King and a Knight. Your sister is mad about 'panju muttai'
(also known as cotton candy). 'panju muttai'-seller has just come and ur sister went out to have
her 'panju muttai'. You are a honest person and have promised yourself to be honest.
But you are also wily. You pacify your conscience that your sister is passing her moves (yes,
that version of chess allows you to pass your move ) and make 'legal' moves !!
You found that, due to unknown reasons, your sister will lose if and only if she loses all her pawns.
you also found that you cannot make moves which kills coins other than pawns when she is away.
Can U Ensure your Win making not more than n legal (or illegal ?) moves before your sister returns ?
The Coins are represented as follows:
Your King = 'K'
Your Knight = 'k'
Enemy Pawns = 'P'
Other Enemy Pieces = 'p'
Empty Location = '.'
Constraints
- Your King can be moved only when your sister is present
- Knight should make only valid chess moves (ie. 'L' shaped moves)
- There will be 1 'K', 1 'k', 0 to 8 'P's, 0 to 8 'p's in the board
Input Format
The first line has an integer t, giving the number of test cases. 1< t <=100.
Each test case described as follows:
First line gives value of 'n'
Next 8 lines contain 8 characters each describing the board.
A Blank line comes before each test case.
Output Format
For Each test case,
In a single line, print 'Yes' if you can win making not more than n moves or 'No' if you cannot.
Sample Input
2
3
...pP...
..P..k.K
p.....p.
...p....
...p....
........
.p......
........
2
.....kp.
........
...Kp...
.P...p..
.p.....p
...p....
........
.p......
Sample Output
Yes
No
Problem Setter: Vijay S
Written for Samhita' 08