The White KnightProblem code: E1 |
All submissions for this problem are available.
You are given a chessboard of size NxN. There is a white knight and several black pawns located on the board. The knight can move similarly to the normal knight in the game of chess; however it can only move towards the right of the board (see the below figure).
The mission of the knight is to capture as many black pawns as possible. Its journey ends when it moves to the rightmost column of the board.
Compute the maximum number of black pawns the white knight can capture.
Input
The first line contains t, the number of test cases (about 10). Then t test cases follow.
Each test case has the following form:
- The first line contains N, the size of the chessboard (4 ? N ? 1000).
- Then N lines follow, each line containing N characters which may be '0', 'K' or 'P', corresponding to the empty cell, the white knight, and the black pawn, respectively. There is exactly one 'K' character in the whole of the board.
Output
For each test case, print in a single line the maximum number of black pawns that can be captured.
Example
Input: 1 5 K.... ..P.. .P... ...P. ..... Output: 2
| Author: | admin |
| Date Added: | 5-06-2009 |
| Time Limit: | 4 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can anyone help with the answer for this one ?
1
5
K....
..P.P
.P...
.....
.....
Need to know if the knight can visit empty node on his way to capture pawns !!
Yes, the knight can visit empty nodes on its way to capture pawns.
@aniruddha plz give me some good test case for this
,my code is working fine but still it gives WA
PLZ PROVIDE SOME GOOD TEST CASES GUYS
Is the text encoding something other than UTF8? I'm beginning to wonder if that's what's tripping me up on this first problem.
Can someone elaborate on the encoding in use? Thanks!
if pawn is present is last column is it 2 b included in no. of pawns captured or not
@nitin Yes, the last column pawn is included.
@John I believe the encoding is ascii. The characters fit within an unsigned character for sure.
i have used BFS to solve the problem,dont know ,iam getting right answeres for all testcases i have tested,but codechef gives it as WA,
plz someone help??
@nitin If you are getting wrong answer then either your approach is wrong or you are making errors in the implementation if your approach is correct.
i have used recurrsion to solve this problem and i have checked my answer for 2-3 test cases it is right but giving me TLE what may be the reason pls help
pls give me some more test case so that i can find out what is going wrong Thanks
You would get a TLE if your algorithm isn't efficient. You might want to find out the worst case complexity of your algorithm and see how it would perform for the current problem.
will DFS or BFS be timeout for this question??
@gautam do check r u using cout,cin then it will give timeout..
@Gautam,probably!!Try dynamic programming instead
@pratik i see that u were getting lots of wrong answeres iniatially then u dod some changes and got right answere,can u plz tell was there something wrong with ur approach or just u were missing 1-2 imp. testcases
Well Thanks for your advices, i tried DP but i gave me TLE , and i use scanf()
what is a kind of programming contest like this? Ask and answer programming contest?
you can have WA with getchar(), use scanf()
@admins: Shouldn't competitors be warned about discussing possible strategies here?
@Rahul I think CodeChef should remove this 'add comment' feature for problems in current contest. They cause way too much trouble in the past 2 months. Many people discuss hints here!
Nice and simple problem!